Codeforces Round 926 C. Sasha and the Casinoの解説です．
問題
次の形式の問題が t ケース与えられる．
整数 k, x, a が与えられる．
a 枚のコインを持ってゲームを始める．あなたはゲームを終了するまで，次の行動を繰り返す．
- コインの所持数が 0 枚である場合ゲームを終了する．
- そうでない場合，コインの所持数以下の正整数 y を自由に選び，コインを y 枚失って賭けを始める．賭けに勝利するとコインを ky 得て，敗北すると何も得られない．
ただし，x 回連続で敗北した直後の賭けで必ず勝利することが保証されている．
あなたが適切に行動すれば，任意の勝利・敗北の起こり方に対し，かならず無限にコインを増やすことができるか1．これを判定せよ．
制約
- 1\leq t\leq 1000
- 各ケースに対し 2\leq k\leq 30, 1\leq x\leq 100, 1\leq a\leq 10^9
解答
便宜的に，賭けに勝利してから次に賭けに勝利するまでを 1 周期と呼びます．ただし最初の周期はゲーム開始時から始めることとします．
判定すべき条件は，「周期を a 枚から始めたときに，次の周期の開始時の枚数を必ず a+1 枚以上にできる」ことと同値です．
これに対する説明として，ここでは a に関する単調性に注目します．すなわち，「a 枚から始めれば必ず1 枚以上増やせる」が真なら「a 枚以上から始めれば必ず1 枚以上増やせる」もまた真であり，逆に「a 枚から始めると最悪の場合 1 枚も増やせない」が真なら「a 枚以下から始めると最悪の場合 1 枚も増やせない」もまた真であることが明らかです．
これにより，前者の場合は増やせるなら増やすことを続けることで帰納的に毎周期 1 枚以上増やせることになり，後者の場合は最悪な場合が起こり続けることで帰納的に毎周期 1 枚も増やせないことになります．
これをふまえて，シミュレーションをします．1 つの周期で行う賭けは高々 x+1 回なので，これをシミュレーションすれば十分です．具体的には次のようになります．
x+1 回繰り返す：
- 今勝利すれば所持数が a+1 枚以上となる最小の枚数を賭ける（所持数から減らす）．
- 所持数が負になった場合，
NOを出力．
YESを出力．
計算量は \mathrm{O}\left(tx\right) です．
- 正確な条件は「任意の枚数のコインを得ることができる」であり，この定義は「任意の整数 n に対し，ある時刻が存在して，その時刻における所持数が n 枚以上となる」こととされています． ↩︎