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

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

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

AtCoder ABC-D AtCoder400点 茶色diff ある量を固定して考える 操作 最大回数・最大個数を求める 操作の流れを単純化する Greedy オーバーフロー 単調性に着目する Greedy:今が良いほど未来も良い 算数と数学

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;
}