外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

F - Trill or Jack or Switch

作成者 sevenc_nanashi

テスター unbakedbread

配点 400 点

実行時間制限
2 秒
メモリ制限
512 MiB

解説

これは「動的計画法」という手法を使うと解くことができます。 すごく雑に言うと、問題を細かく分割し、その分割した他の問題を使って最終的な問題を解く、といった手法です。
(有名な例で言うと、「重さを超えない範囲で可能な限り価値の高いものを選ぶ」というナップサック問題などがあります。この動画が参考になるかも?)

この問題では、現在時刻ttの他に、「左手の指の位置」、「右手の指の位置」、「時刻ttで左手でノートを押したか」「時刻ttで右手でノートを押したか」の4つの情報が重要です。
また、時刻ttにかかるコストは、t−1t-1時点での状態(前述の4つの情報)のみに依存するため、t−1t-1より前の状態は無視してよいことがわかります。また、同じ状態でコストが最小でないものを残しておく必要はありません。
よって、「時刻ttで状態が〇〇であるときのコストの最小値(あるいは到達不可)」を元に、「時刻t+1t+1で状態が〇〇であるときのコストの最小値(あるいは到達不可)」を計算していき、最終的に「時刻NNでのコストの最小値(状態は問わない)」が答えとなります。

より詳しく書くと以下のようになります:

dp[t][(l,r,llast,rlast)]=時刻tの処理後、左手の指がl番目のレーンにあり、右手の指がr番目のレーンにあり、時刻tで左手でノートを押したかがllast、時刻tで右手でノートを押したかがrlastのときの最小コスト\begin{align*} dp[t][(l, r, l_\text{last}, r_\text{last})] =& \text{時刻}t\text{の処理後、} \\ & \text{左手の指が}l\text{番目のレーンにあり、} \\ & \text{右手の指が}r\text{番目のレーンにあり、} \\ & \text{時刻$t$で左手でノートを押したかが}{l_\text{last}}\text{、} \\ & \text{時刻$t$で右手でノートを押したかが}{r_\text{last}}\text{のときの最小コスト} \end{align*}

デフォルト値は∞\infty、ただしdp[t=0][(l=1,r=4,llast=No,rlast=No)]=0dp[t=0][(l = 1, r = 4, l_\text{last} = \text{No}, r_\text{last} = \text{No})] = 0とします。 遷移は以下のように行います。また、遷移先の状態ですでにコストが計算されている場合は、新しく試すコストと比較して小さい方を採用します。(よくchminと呼ばれます)

  • ノートがないとき:
    • 一つ前の状態(l,r,llast,rlast)(l, r, l_\text{last}, r_\text{last})から、(l,r,No,No)(l, r, \text{No}, \text{No})に追加コストなしで遷移します。
  • ノートが一つあるとき(位置はppとします):
    • 左手で押す場合:
      • (l,r,llast,rlast)(l, r, l_\text{last}, r_\text{last})から(p,r,Yes,No)(p, r, \text{Yes}, \text{No})に遷移します。追加で∣p−l∣×A+B|p - l| \times A + B、もしllast=Yesl_\text{last} = \text{Yes}ならさらにCCのコストがかかります。
    • 右手で押す場合:
      • (l,r,llast,rlast)(l, r, l_\text{last}, r_\text{last})から(l,p,No,Yes)(l, p, \text{No}, \text{Yes})に遷移します。追加で∣p−r∣×A+B|p - r| \times A + B、もしrlast=Yesr_\text{last} = \text{Yes}ならさらにCCのコストがかかります。
  • ノートが二つあるとき(位置はp1,p2p_1, p_2とします):
    • 左手でp1p_1、右手でp2p_2を押す場合:
      • (l,r,llast,rlast)(l, r, l_\text{last}, r_\text{last})から(p1,p2,Yes,Yes)(p_1, p_2, \text{Yes}, \text{Yes})に遷移します。追加で∣p1−l∣×A+∣p2−r∣×A+2B|p_1 - l| \times A + |p_2 - r| \times A + 2B、もしllast=Yesl_\text{last} = \text{Yes}ならさらにCC、もしrlast=Yesr_\text{last} = \text{Yes}ならさらにCCのコストがかかります。
    • 左手でp2p_2、右手でp1p_1を押す場合:
      • (l,r,llast,rlast)(l, r, l_\text{last}, r_\text{last})から(p2,p1,Yes,Yes)(p_2, p_1, \text{Yes}, \text{Yes})に遷移します。追加で∣p2−l∣×A+∣p1−r∣×A+2B|p_2 - l| \times A + |p_1 - r| \times A + 2B、もしllast=Yesl_\text{last} = \text{Yes}ならさらにCC、もしrlast=Yesr_\text{last} = \text{Yes}ならさらにCCのコストがかかります。

各時刻で状態はたかだか4×4×2×2=644 \times 4 \times 2 \times 2 = 64通り、遷移は22通りしかないので、時刻ごとに全ての状態を管理することができます。 計算量はO(N)O(N)です。

実装例(Ruby、1079ms)

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。