ABC128-F:Frog Jump - 思考の墓場

コンテスト中に解き切りたかったけど、細かいところも少し要求されるので厳しかったかな...。

問題

解法

蓮以外の点に行かないようにしないといけないので、まず $0 \lt B \lt A\leq N-1$ という条件が得られる。この下で、 $A,B$ を決めたときの動きを観察すると、以下のように書ける。
$0,A,A-B,2A-B,2A-2B,\cdots, (k+1)A-kB=N-1$
ここで、 $C=A-B$ とおけば、
$0,A,C,A+C,2C \cdots A+kC = N-1$
と書ける。つまり、 $k,C$ さえ決めれば動きが定まり、 $kC\lt N-1$ より、あり得る $(k,C)$ の組を全部試しても、各組を $O(1)$ で調べることができれば全体で $O(N\log{N})$ で間に合う(計算量が調和級数になるやつ)。実際、 $C$ を固定して $k$ を1増やすと、新たに $s_{N-1-kC},s_{kC}$ に訪れることができるようになるから、各 $C$ に対して $k$ の小さい順に探索を進めればよい。
問題は、一度訪れた蓮の上には再度訪れることができないという条件だ。再度訪れることがあり得る $(k,C)$ については探索してはいけない。このようなことが起こる $(k,C)$ の条件を考えよう。動き方から、このようなことがあるとしたら、非負整数の組 $(k_1,k_2)$ が存在して、 $k_1C = A+Ck_2$ という等式が成り立つはずである。これは $k_1=k_2+\frac{A}{C}$ と変形できるので、まず $A$ が $C$ で割り切れると危険だということがわかる。さらに、この等式を満たし、かつ $k_1$ が最小になるような $(k_1,k_2)$ の組は当然 $(\frac{A}{C},0)$ である。このことより、 $\frac{A}{C} \gt k$ であれば、 $A$ が $C$ で割り切れても、蓮を再度訪れるということが起こる前に $N-1$ の蓮にたどりついてゲームが終了する。したがって、条件を満たす $(k,C)$ の組の条件は以下の $1$ と $2$ が同時に成り立つことである。