light-stick

解説

問題の概要

• 円環状に並んだ $N$ 個の位置に色 $C_1, C_2, \dots, C_N$ が割り当てられているペンライトがあります。
• ボタン L を押すと左隣、R を押すと右隣に移動します（添字は循環）。
• 初期状態では $C_1$ が点灯しています。
• ライブで $K$ 曲あり、$i$ 曲目では色 $T_i$ にしなければなりません。
• 全曲を通して必要なボタン押下回数の最小値を求める問題です。

想定解法の概要

前処理

任意の位置 $j$ と色 $x$ に対して、

• 左に回ったとき最寄りの $x$ までの距離 L[j][x]
• 右に回ったとき最寄りの $x$ までの距離 R[j][x]

を求めておきます。
これは「2 周分の配列を走査しながら直前/直後の出現位置を保持する」ことで、$O(NM)$ 時間で計算できます。

DP

dp[i][j] を「$i$ 曲目を終えた時点でインデックス $j$ にいるときの押下回数の最小値」と定義します。

• 遷移は「現在の色 $T_i$ を表す位置 $j$ から、次の色 $T_{i+1}$ への移動」です。
• このとき見るべき候補は「左右の最近傍の出現位置のみ」で十分です。
  • 同じ方向にさらに奥の出現を選んでも、その手前の最近傍を経由した方が常に押下回数が少なくなるためです。
• よって dp[i][j] からは最大 2 通りの遷移を考えればよいです。

最後に dp[K][*] のうち、色が $T_K$ になっているものの最小値が答えです。

計算量

• 前処理：$O(NM)$
• DP：$O(NK)$（各状態から左右高々 2 遷移）
• 全体の計算量が $O(NM + NK)$ となり制約下で十分高速に動作します。

正当性

• 遷移先として「左右最近傍の位置のみを考えればよい」ことが鍵です。
  • より遠い出現に直接移動するより、最近傍に寄ってから後で移動した方がコストが小さいか等しいからです。
• したがってこの DP は最適解を漏らさず探索でき、最小値が正しく得られます。

実装例は以下のようになります。