けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 180 D - Takahashi Unevolved (茶色, 400 点)

2 種類の操作がある系の問題!こういうのは操作の手順を単純化して考えられる場合が多い

問題概要

正の整数  X が与えられる。これに対して以下の 2 種類の操作のいずれかを繰り返し行なっていく

  •  X A 倍する
  •  X B を足す

 X Y 以上となってはならない。操作は最大で何回まで行うことができるか?

制約

  •  1 \le X \lt Y \le 10^{18}
  •  2 \le A \le 10^{9}
  •  1 \le B \le 10^{9}

考えたこと

操作が複数種類あるような問題では、操作の流れを単純化できる場合が多い気がする。今回も

  • 先に何度か  A 倍してから
  •  Y 以上になるまでの間  B を足していく

というふうにすればよいことがいえる。まず大前提として、

 X がいかなる値であっても、 AX X + B のうちの小さい方に操作を行う方がよい」

ということがいえる (Greedy)。操作後の  X が小さいことによって損することがないためだ。より具体的には

  •  (A - 1)X \ge B のときは、「 +B」を選択
  •  (A - 1)X \lt B のときは、「 ×A」を選択

というふうにするのがよい。そして、 X が大きければ大きいほど  (A - 1)X の値は大きくなっていくので、

 X が小さいうちは  ×A するのがよくて、 X がある一定以上大きくなったら  +B するのがよい」

という風になっていることがわかる。この閾値を直接求めてもいいが、実装上は次のようにすると楽そう。


 i = 0, 1, 2, \dots に対して

  •  X i 回、「 ×A」して
  • その後  Y 以上とならない範囲でひたすら  +B をする

ことによって何回まで操作を行えるかを求める。その最大値をとる。


なお、 X に対して  Y 以上とならないように何回まで「 +B」できるかについては、次の式で求められる。

 (Y - 1 - X) / B

計算量は、確認すべき  i O(\log Y) 通りなので、 O(\log Y) となる。

コード

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    long long X, Y, A, B;
    cin >> X >> Y >> A >> B;
    long long res = 0;
    long long cnt = 0;
    while (X < Y) {
        long long tmp = cnt + (Y - X - 1) / B;
        chmax(res, tmp);
        if (X >= (Y + A -1) / A) break; // これ以上 A 倍したら Y 以上
        X *= A;
        ++cnt;
    }
    cout << res << endl;
}