Rabbit and turtle 解説!

皆様どうもこんにちは！ばるとーくです！
今回は問題「Rabbit and turtle」の解説をしていきます！

問題

問題文

今から、うさぎとかめが、 $10^{100}$ ターンでどれだけ進めるか勝負することにした。
スタート時はうさぎ・かめのどちらも進んだ距離は $0$ とする。
うさぎとかめはそれぞれ以下のルールに従って進む。

• うさぎ：最初のターンは $A$ だけ進み、疲労度を $D$ にする。
  その後，毎ターンの行動を以下のように定める。
  • 疲労度が $0$ より大きいときは進まず、疲労度を $R$ 減少させる。
  • 疲労度が $0$ 以下の時は $A$ だけ進み、疲労度を $D$ 増加させる。
• かめ：毎ターン $B$ だけ進む。

このとき、どちらが勝利したか、すなわち、$10^{100}$ ターン後にどちらがより長い距離を進んだか答えよ。
なお、引き分けの可能性もあるとする。

$T$ 個のテストケースが与えられるので、それぞれについて答えよ。

制約

$1 \leqq B \leqq A \leqq 10^{9}$
$1 \leqq R \leqq D \leqq 10^{9}$
$1 \leqq T \leqq 10^5$

No.3633 Rabbit and turtle - yukicoder

競技プログラミングの練習サイト

yukicoder.me

解説

大前提として、$10^{100}$ ターン後の状態を聞いているので愚直にシミュレーションしてはいけません。
$10^{100}$ は "googol(グーゴル)" と呼ばれる非常に巨大な数であるため、到底計算しきることはできません。

そこでこの問題は、うさぎの位置を「経過ターン数の閉じた式」で表して、平均速度を比較する という方針で解きます。
ポイントは、本問のルールでは疲労度を「$D$ にする」のではなく「$D$ 増加させる」になっている点です。
回復しきれずに $0$ を下回った分（オーバーシュート）が次の疲労度に持ち越されるため、待機ターン数が一定になりません。
ここが素直な実装を許さない肝になっています。

この持ち越しを追いかけるのは一見大変ですが、ルールの書き方を少し変えるだけで見通しが良くなります。
$P = D + R$ とおいて、うさぎの行動を次のように読み替えてみましょう。

毎ターン疲労度を $R$ 減らし、動いたターンにはさらに $P$ 増やす。

動かないターンは $-R$ でそのまま一致し、動くターンは $-R + P = +D$ なのでこちらも一致します。
初期疲労度を $0$ とすればターン $1$ は $0 - R + P = D$ となり、「最初のターンは疲労度を $D$ にする」という規定とも辻褄が合います。

この読み替えのうれしいところは、疲労度が 動作回数と経過ターン数だけ で決まることです。
ターン $\tau$ 終了時点までにうさぎが動いた回数を $m(\tau)$ とおくと、そのときの疲労度は

$$f(\tau) = m(\tau)P - R\tau$$

と書けます。オーバーシュートの持ち越しは、この式が自動的に面倒を見てくれます。

さて、ターン $\tau$ に動く条件は「直前の疲労度が $0$ 以下であること」、すなわち $f(\tau-1) \leqq 0$ です。
上の式を代入すると、条件は

$$m(\tau-1) \leqq \frac{R(\tau-1)}{P}$$

と書き直せます。ここから、動作回数そのものが床関数 $1$ つで表せることが示せます。

補題：任意の $\tau \geqq 1$ について

$$m(\tau) = \left\lfloor \frac{R(\tau-1)}{P} \right\rfloor + 1 = \left\lfloor \frac{R\tau + D}{P} \right\rfloor$$

$2$ つの式が等しいことは、$\lfloor x/P \rfloor + 1 = \lfloor (x+P)/P \rfloor$ に $x = R(\tau-1)$ を代入し、$P - R = D$ を使えば分かります。

証明は $\tau$ に関する帰納法によります。
$\tau = 1$ のときは $m(1) = \lfloor 0 \rfloor + 1 = 1$ であり、最初のターンは必ず動くので正しいです。
$\tau - 1$ で成立を仮定し、$k = \left\lfloor R(\tau-1)/P \right\rfloor$ とおきます。
$R \leqq P$ より $\left\lfloor R(\tau-1)/P \right\rfloor - \left\lfloor R(\tau-2)/P \right\rfloor$ は $0$ か $1$ なので、仮定した $m(\tau-1) = \left\lfloor R(\tau-2)/P \right\rfloor + 1$ は $k$ か $k+1$ のいずれかです。

• $m(\tau-1) = k$ のとき、上の条件が成り立つのでターン $\tau$ に動き、$m(\tau) = k+1$ となります
• $m(\tau-1) = k+1$ のとき、上の条件が成り立たないので動かず、$m(\tau) = k+1$ のままです

どちらの場合も $m(\tau) = k+1$ となり、$\tau$ でも補題が成立します。

これで、任意のターン $\tau$ における両者の位置が直接求まりました。

$$\text{うさぎの位置} = A\left\lfloor \frac{R\tau + D}{P} \right\rfloor, \qquad \text{かめの位置} = B\tau$$

なお、この式は傾き $R/P$ の直線を格子で切る形をしており、ブレゼンハムの直線描画と同じ構造です。
周期を数え上げることなく、任意の $\tau$ について $O(1)$ で評価できます。

床関数は $R\tau/P$ との差が $1$ 未満なので、うさぎの位置は $AR\tau/P$ から高々 $A$ しかずれません。
したがって長期的な速度はうさぎが $AR/P$、かめが $B$ となり、分母を払うと勝敗の大筋は $AR$ と $BP$ の比較で決まります。

• $AR > BP$ のとき：うさぎの勝ち
• $AR < BP$ のとき：かめの勝ち

$AR \neq BP$ であれば $1$ ターンあたりの差は $|AR - BP| / P \geqq 1/P$ 以上あり、これに $10^{100}$ を掛ければ揺らぎの上限 $A \leqq 10^9$ を圧倒的に上回ります。
よってこの $2$ ケースは即座に判定して構いません。

問題はこの $2$ つが等しいとき（平均速度が同じとき）です。

単純に疲労度を $D$ に戻すルールであれば、平均が同じなら常に引き分けになります。
しかし本問は持ち越しがあるため、うさぎがジャンプで先行し、かめがコツコツ詰めるという振動が生じます。
平均が同じでも途中では差が $0$ をまたいで揺れ、終了するタイミング次第で、うさぎ・かめ・引き分けのいずれにもなり得るのです。

例として $A=7,\ B=2,\ D=5,\ R=2$ を考えます。
$P = 7$ で $AR = BP = 14$ なので平均速度は等しく、位置の差を追うと次のようになります。

$10^{100} \bmod 7 = 4$ なので、ちょうど差が $-1$ になる地点で勝負が終わり、かめの勝ちになります。

一般の場合も、閉じた式のおかげで簡単に処理できます。
$r = \tau \bmod P$ として $\tau = qP + r$ と分解すると、

$$\left\lfloor \frac{R\tau + D}{P} \right\rfloor = \left\lfloor \frac{qRP + Rr + D}{P} \right\rfloor = qR + \left\lfloor \frac{Rr + D}{P} \right\rfloor$$

なので、両者の位置は

$$\text{うさぎ} = AqR + A\left\lfloor \frac{Rr + D}{P} \right\rfloor, \qquad \text{かめ} = BqP + Br$$

となります。いまは $AR = BP$ を仮定しているので $AqR = BqP$ が打ち消し合い、結局

$$A\left\lfloor \frac{Rr + D}{P} \right\rfloor \quad \text{と} \quad Br \qquad (r = 10^{100} \bmod P)$$

の大小を比べるだけで、うさぎ / かめ / 引き分け が決まります。
$10^{100} \bmod P$ は $10$ を $100$ 回掛けるだけで求まります。

なお、$P = D+R$ はうさぎの真の最小周期（$P / \gcd(D, R)$ ターン）とは限りませんが、上の変形は $P$ の最小性をどこにも使っていないため問題ありません。
$\gcd$ を計算する必要はありません。

最後に注意点を $1$ つ挙げておきます。
サンプル $3$ の 4 2 1 1 は $AR = BP = 4$ かつ答えが tie であるため、「平均速度が等しければ引き分け」と誤解したまま提出しても、サンプルはすべて通ってしまいます。
本問の核心はこの最後の場合分けにあるので、必ず上の比較まで実装してください。

全体の計算量

$1$ ケースあたり、必要なのは $10^{100} \bmod P$ の計算だけなので $O(\log)$ です。
$T \leqq 10^5$ ケースあっても余裕で間に合います。

なお、各種積の最大値は $BP$ および $Br$ の $2 \times 10^{18}$ 程度で、long long（64bit 整数）に収まります。
$r < P \leqq 2 \times 10^9$ および $\left\lfloor (Rr+D)/P \right\rfloor \leqq R$ から、$Rr + D$ や $A\left\lfloor (Rr+D)/P \right\rfloor$ も同様に収まります。

想定解は yukicoder の解説ページを参考にしてください．