AtCoder Beginner Contest 180 [ D - Takahashi Unevolved ] をPythonで解く（400点、🟫茶diff）

問題

atcoder.jp

解法

• カコモンジムに行くと強さがA倍、経験値+1
• AtCoderジムに行くと強さが+B、経験値+1

強さXとして、A * XとX + Bを比較して小さい方を行えば良いが、制約条件から愚直にシミュレーションすると計算量がO(10⁸)を超えてしまう。

まず、カコモンジムに何回か行ってからAtCoderジムに何回か行くという行動が常に最適であることに気がつく必要がある。

• AtCoderジムに行ってカコモンジムに行く場合
  X + B -> A * X + A * B
• カコモンジムに行ってAtCoderジムに行く場合
  A * X -> A * X + B

よって、カコモンジムにいってからAtCoderジムに行く方が数が小さくなる。

A * X が何回実行したら、X + Bを超えてしまうかを計算する必要があるが、これは単純にシミュレーションする。
2 <= Aであるから、A * X は最大64回程度しか回らないから、計算量を心配する必要はない。

つぎにX + BがY - 1を超えるまで、何回足せるかを計算する必要がある。
こちらはシミュレーションだと計算量が多すぎる場合がある。
ゆえに割り算する。

実装

参考

youtu.be

snukeさんの解説を基に実装。