450.1

1000

1列に並んだマスに数字が書かれている。初期位置は左端。現在位置から右にある任意のマスに移動し、その区間に書かれている総和を得点とし、次に左にある任意のマスに移動し、その区間に書かれている総和を得点とする。これをKステップ繰り返し、得点を最大化せよ、という問題。ただし途中で得点はマイナスになってはいけない。

もし初期位置が任意のマスに選べるのなら、得点が最大になる区間を探して、そこを反復移動するだけ。初期位置は左端なので、いかにそのような区間に効率良く移動するか、という問題になる。(ただしステップ数が少ない時には移動しない方がいいこともある。)

取り敢えずすべてのマスについて、得点が最大値になる移動を両側について求める。その移動について、自分のマスに戻ってくるのが最適な場合、その区間を覚えておく。このような区間は重ならないことが証明できる。これらの区間のどれに乗っているかを状態としてダイクストラ(のようなもの)をやる。初期位置がどの区間の端にもならない(要はマイナスのスコア)の場合には、可能な区間の端に移動しておく必要がある。

状態遷移については、自分より右のマスについて、どこかの区間の右端になっている場合、その区間に移動するかどうかを判定する。現在の区間よりも反復による実入りの良くない区間は無視する。(これにより区間の数は高々マス数であることとあわせると、O(N^2)くらいの遷移しか起こらない。)移動する際に得点がマイナスにならないようにするために、何ステップか自分の区間で反復しておく。さらに反対側についてもチェックする。

実際には反対側をチェックして実入りのあるものがある場合、その分だけ状態が増えてひどいことになるので、同じ区間に落ちる時に、到達ステップと到達スコアから明らかに悪いものを捨てる必要がある。(この辺の実装がかなりひどいので、もっとすっきり整理できるような気はしているが...。)