解説
これは「動的計画法」という手法を使うと解くことができます。
すごく雑に言うと、問題を細かく分割し、その分割した他の問題を使って最終的な問題を解く、といった手法です。
(有名な例で言うと、「重さを超えない範囲で可能な限り価値の高いものを選ぶ」というナップサック問題などがあります。この動画が参考になるかも?)
この問題では、現在時刻tの他に、「左手の指の位置」、「右手の指の位置」、「時刻tで左手でノートを押したか」「時刻tで右手でノートを押したか」の4つの情報が重要です。
また、時刻tにかかるコストは、t−1時点での状態(前述の4つの情報)のみに依存するため、t−1より前の状態は無視してよいことがわかります。また、同じ状態でコストが最小でないものを残しておく必要はありません。
よって、「時刻tで状態が〇〇であるときのコストの最小値(あるいは到達不可)」を元に、「時刻t+1で状態が〇〇であるときのコストの最小値(あるいは到達不可)」を計算していき、最終的に「時刻Nでのコストの最小値(状態は問わない)」が答えとなります。
より詳しく書くと以下のようになります:
dp[t][(l,r,llast,rlast)]=時刻tの処理後、左手の指がl番目のレーンにあり、右手の指がr番目のレーンにあり、時刻tで左手でノートを押したかがllast、時刻tで右手でノートを押したかがrlastのときの最小コスト
デフォルト値は∞、ただしdp[t=0][(l=1,r=4,llast=No,rlast=No)]=0とします。
遷移は以下のように行います。また、遷移先の状態ですでにコストが計算されている場合は、新しく試すコストと比較して小さい方を採用します。(よくchminと呼ばれます)
- ノートがないとき:
- 一つ前の状態(l,r,llast,rlast)から、(l,r,No,No)に追加コストなしで遷移します。
- ノートが一つあるとき(位置はpとします):
- 左手で押す場合:
- (l,r,llast,rlast)から(p,r,Yes,No)に遷移します。追加で∣p−l∣×A+B、もしllast=YesならさらにCのコストがかかります。
- 右手で押す場合:
- (l,r,llast,rlast)から(l,p,No,Yes)に遷移します。追加で∣p−r∣×A+B、もしrlast=YesならさらにCのコストがかかります。
- ノートが二つあるとき(位置はp1,p2とします):
- 左手でp1、右手でp2を押す場合:
- (l,r,llast,rlast)から(p1,p2,Yes,Yes)に遷移します。追加で∣p1−l∣×A+∣p2−r∣×A+2B、もしllast=YesならさらにC、もしrlast=YesならさらにCのコストがかかります。
- 左手でp2、右手でp1を押す場合:
- (l,r,llast,rlast)から(p2,p1,Yes,Yes)に遷移します。追加で∣p2−l∣×A+∣p1−r∣×A+2B、もしllast=YesならさらにC、もしrlast=YesならさらにCのコストがかかります。
各時刻で状態はたかだか4×4×2×2=64通り、遷移は2通りしかないので、時刻ごとに全ての状態を管理することができます。
計算量はO(N)です。
実装例(Ruby、1079ms)