解法
とすると、実際の遷移は図のようになります。
ということで、距離おきに、前から
個、後ろから
個の蓮の得点を得ると決めた時の
は自動的に決まります。
をある値に固定したとき、
はだいたい
個の候補が存在し、
について全探索を行っても
におさまります。この全探索は、
が小さいパターンから順に、距離
ごとに前後から得点を足していくことで、十分高速に計算することができます。
あとは、が条件を満たす部分(つまり
)について全探索を行えば、その中で最も得点が高かったものを選ぶことで答えが求まります。
が
で割り切れるときのみ注意が必要です。このパターンでは、前から見ている蓮と後ろから見ている蓮が被った、もしくは交差した時点で探索を終了する必要があります。
感想
今回ほぼ自力で解くことができたのですが、当時、F問題に十分時間を割けていたらどうだったのでしょうか…
