phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

ABC128 F. Frog Jump

問題

N個の蓮が一列に並んでおり、0~N-1まで番号がついている。
最初、0の蓮におり、以下の手順に従ってゲームを行う。

1. 正の整数A, Bを決める。得点は最初は0。
2. 現在の位置xとして、y=x+Aとする。xの蓮を消してyに移動する
このとき、y=N-1ならゲーム終了。そうでなく、yの蓮があるなら得点s_yを得る。yの蓮がない場合は得点を10^100減らして終了。
3. 現在の位置xとして、y=x-Bとする。xの蓮を消してyに移動する
このとき、y=N-1ならゲーム終了。そうでなく、yの蓮があるなら得点s_yを得る。yの蓮がない場合は得点を10^100減らして終了。
4. 手順2に戻る

最終得点をできるだけ大きくしたい場合、最終得点はいくらになるか。

制約

  • 3 <= N <= 10^5
  • -10^9 <= s_i <= 10^9
  • s_0 = s_{N-1} = 0

解法

問題文から以下がわかる。
経路の動きとしては「0 -> A -> A-B -> 2A-B -> 2A-2B -> ... -> N-1」のように推移する。
また、手順3ではN-1に達することはできないので、手順2の時にN-1にたどり着くように終わらないといけない。よって「(x+1)*A-x*B = N-1」となるようなxがある。

単純にA,Bをループで回すとxはO(1)で決まるが、スコアの計算にO(N)かかってしまう。全体としてはO(N^3)で間に合わない。

ここで、「(x+1)*A-x*B = N-1」を変形して「x(A-B)+A = N-1」と考えて、xとA-Bでループを回すことを考える。(これに気付くためにはAとx、Bとxとかも考えていればたどり着ける?)

C=A-Bとして、これはループを回すとして固定して考える。
x=1からループを回すと、AとBが決まるので、どういう蓮を通っているかを表示してみると、左右からCずつx個取るような対称形の法則性がでてくる。

この法則性を活用すると、取る蓮が同じになるようなものをまとめて、かつ、xを順番に増やすことで効率的に求めていける。

気を付けることとしては、
・x*Cが範囲を超えないようにする
・A,Bの条件をちゃんと満たすかチェックする
・左右から取っていったときに、すでになくなった蓮だった場合は条件を満たせないので、すでに取った蓮かどうかを記録しながらxを増やしていく

Cとxのループは、ΣN/iのような形になるのでO(NlogN)の計算量になる。