概要

石 \(1\) から石 \(N\) まで、最大 \(K\) 個先の石にジャンプしながら進むとき、着地した石のコストの合計を最小化する問題です。動的計画法（DP）とスライディングウィンドウ最小値（単調デック）を組み合わせて効率的に解きます。

考察

DP の定式化

石 \(i\) に到達するまでの最小累計コストを \(dp[i]\) とすると、石 \(i\) には石 \(\max(1, i-K)\) から石 \(i-1\) のいずれかからジャンプして来られるので、以下の漸化式が成り立ちます：

\[dp[i] = A_i + \min_{j \in [\max(0,\, i-K),\, i-1]} dp[j]\]

初期値は \(dp[0] = A_1\)（0-indexed で石 \(1\) に対応）です。

素朴なアプローチの問題点

各 \(dp[i]\) を計算するために \(dp[j]\)（\(j\) は最大 \(K\) 個）の最小値を毎回ナイーブに求めると、全体で \(O(NK)\) の計算量になります。\(N\) が最大 \(10^6\)、\(K\) も最大 \(N-1\) なので、最悪 \(O(N^2)\) となり TLE になります。

解決策：スライディングウィンドウ最小値

「直前の最大 \(K\) 個の中から最小の \(dp\) 値を高速に取得する」という操作は、単調デック（Monotone Deque） を使えば各要素あたり \(O(1)\)（償却）で処理できます。

アルゴリズム

単調デックは「デックの先頭が常にウィンドウ内の最小値のインデックスを保持する」ように管理するデータ構造です。

具体的な手順：

1. \(dp[0] = A_0\) とし、デックにインデックス \(0\) を入れる。
2. \(i = 1, 2, \ldots, N-1\) について以下を繰り返す：
   • ウィンドウ外の除去: デックの先頭が \(i - K\) より小さい（＝ジャンプ範囲外）なら先頭から除去する。
   • DP の更新: デックの先頭のインデックスを \(f\) として \(dp[i] = A_i + dp[f]\)。
   • 単調性の維持: デックの末尾から、\(dp\) 値が \(dp[i]\) 以上のインデックスを除去し、\(i\) を末尾に追加する。
3. \(dp[N-1]\) が答え。

具体例

\(N = 5,\, K = 2,\, A = [3, 1, 5, 2, 4]\) の場合：

\(i\)	遷移元の範囲	デック先頭の \(dp\)	\(dp[i]\)
0	—	—	\(3\)
1	\(\{0\}\)	\(dp[0]=3\)	\(1+3=4\)
2	\(\{0,1\}\)	\(dp[0]=3\)	\(5+3=8\)
3	\(\{1,2\}\)	\(dp[1]=4\)	\(2+4=6\)
4	\(\{2,3\}\)	\(dp[3]=6\)	\(4+6=10\)

答えは \(dp[4] = 10\) です。

計算量

• 時間計算量: \(O(N)\) — 各インデックスはデックに最大 1 回追加・1 回削除されるため、全体で \(O(N)\)。
• 空間計算量: \(O(N)\) — \(dp\) 配列とデックにそれぞれ最大 \(O(N)\)。

実装のポイント

• デックには インデックス を格納し、\(dp\) 値の比較はそのインデックスを使って行います。こうすることでウィンドウ外かどうかの判定とDP値の比較を両方扱えます。

• デックの末尾から除去する条件は dp[dq[-1]] >= dp[i]（等号を含む）です。等号を含めることで、同じ値が複数ある場合に新しい方だけを残し、ウィンドウから外れにくくできます。

• Python では collections.deque の popleft() / pop() / append() がすべて \(O(1)\) なので、効率的に実装できます。

• \(N\) が最大 \(10^6\) と大きいため、sys.stdin.read() で入力を一括読み込みすることで I/O を高速化しています。

  ソースコード

import sys
from collections import deque

def main():
    input_data = sys.stdin.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = list(map(int, input_data[2:2+N]))
    
    # dp[i] = minimum cost to reach stone i
    # dp[i] = A[i] + min(dp[j] for j in range(max(0, i-K), i))
    # Use a sliding window minimum with a deque
    
    dp = [0] * N
    dp[0] = A[0]
    
    dq = deque()  # stores indices, dp values in increasing order
    dq.append(0)
    
    for i in range(1, N):
        # Remove elements out of window
        while dq and dq[0] < i - K:
            dq.popleft()
        
        dp[i] = A[i] + dp[dq[0]]
        
        # Maintain monotonic deque
        while dq and dp[dq[-1]] >= dp[i]:
            dq.pop()
        dq.append(i)
    
    print(dp[N-1])

main()

---

この解説は claude4.6opus-thinking によって生成されました。