ABC 128 F - Frog Jump

• 問題
• AC

$A, B \in {\mathbb N}$が与えられたときの経路は（$N-1$にたどりつくなら）

$0, A, A-B, 2A-B, ..., kA-(k-1)B \: (=N-1)$

のようになっている。$C:=A-B$とすると$B+kC=N-1$が成り立つので、逆に$k, C$が与えられると$B = N-1-kC$, $A= N-1-(k-1)C$となって経路が決まることになる。$f(k, C)$をこの経路の最終得点とする。$A, B > 0 \Leftrightarrow kC < N-1$だから、$kC < N-1$を満たすような${\mathcal O}(N\log N)$通りの$k, C$について$f(k, C)$を求めればよい。

$f$の漸化式について考える。$k, C$が与えられたときの経路は

$0, N-1-(k-1)C, C, N-1-(k-2)C, 2C, ..., N-1-C, (k-1)C, N-1$

であり、$k$を1増やすと

$0, N-1-kC, C, N-1-(k-1)C, 2C, ..., N-1-C, kC, N-1$

となる。差分を見ると$f$の漸化式は

$f(k+1, C) = f(k, C) + S_{N-1-kC}+S_{kC}$

と書けるので、これに従ってDPすればよい。

ただし、同じ位置を2回通ってしまうパターンを除く必要がある。上の経路を観察すると、同じ位置を2回通るのは$x, y \in \{1, ..., k-1\}$が存在して$N-1-xC = yC$となる場合であり、これは$z \in \{2, 3, ..., 2(k-1)\}$が存在して$N-1 = zC$が成り立つのと同値である。つまり、$C$が$N-1$を割り切り、かつ $2 \le (N-1)/C \le 2(k-1)$である場合を除けばよい。

超えるべきハードルがいくつかあるので、コンテスト中に解けるようになるのは大変そう。