ABC128 F - Frog Jump - ツバサの備忘録

解法

$A - B = X$ とすると、実際の遷移は図のようになります。
f:id:emtubasa:20190821225843p:plain
ということで、距離 $X$ おきに、前から $k$ 個、後ろから $k$ 個の蓮の得点を得ると決めた時の $A$ は自動的に決まります。
$X$ をある値に固定したとき、 $k$ はだいたい $N/X$ 個の候補が存在し、 $X$ について全探索を行っても $O(N log N)$ におさまります。この全探索は、 $k$ が小さいパターンから順に、距離 $X$ ごとに前後から得点を足していくことで、十分高速に計算することができます。
あとは、 $A,X$ が条件を満たす部分(つまり $A \gt X$ )について全探索を行えば、その中で最も得点が高かったものを選ぶことで答えが求まります。
$N-1$ が $X$ で割り切れるときのみ注意が必要です。このパターンでは、前から見ている蓮と後ろから見ている蓮が被った、もしくは交差した時点で探索を終了する必要があります。

感想

今回ほぼ自力で解くことができたのですが、当時、F問題に十分時間を割けていたらどうだったのでしょうか…