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)の計算量になる。

メモ

• 取れる形は対称となる
  • ちょうどゴールしないといけないので、スタート直後は+A、ゴール直前は+Aで、A,Bの繰り返しなので対称な形になる
• スタートからA-Bずつ進む、ゴールからA-Bずつ戻る
  • 対称な形を維持して左右からA-Bだけ取るような形を作れる
• A-Bを何回行うか？を決めると、対称でないといけない制約からA,Bが決まる
• A-Bと、A-Bが何回か？をループで回せばよい
  • 何回か？は調和級数の形からO(NlogN)