2 種類の操作がある系の問題!こういうのは操作の手順を単純化して考えられる場合が多い
問題概要
正の整数 が与えられる。これに対して以下の 2 種類の操作のいずれかを繰り返し行なっていく
- を 倍する
- に を足す
が 以上となってはならない。操作は最大で何回まで行うことができるか?
制約
考えたこと
操作が複数種類あるような問題では、操作の流れを単純化できる場合が多い気がする。今回も
- 先に何度か 倍してから
- 以上になるまでの間 を足していく
というふうにすればよいことがいえる。まず大前提として、
「 がいかなる値であっても、 と のうちの小さい方に操作を行う方がよい」
ということがいえる (Greedy)。操作後の が小さいことによって損することがないためだ。より具体的には
- のときは、「」を選択
- のときは、「」を選択
というふうにするのがよい。そして、 が大きければ大きいほど の値は大きくなっていくので、
「 が小さいうちは するのがよくて、 がある一定以上大きくなったら するのがよい」
という風になっていることがわかる。この閾値を直接求めてもいいが、実装上は次のようにすると楽そう。
各 に対して
- を 回、「」して
- その後 以上とならない範囲でひたすら をする
ことによって何回まで操作を行えるかを求める。その最大値をとる。
なお、 に対して 以上とならないように何回まで「」できるかについては、次の式で求められる。
計算量は、確認すべき が 通りなので、 となる。
コード
#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; }