概要

石1から石Nまで、一度のジャンプで最大K個先までの石に移動できるとき、通過する石の値の合計を最小化する問題です。

考察

素朴な動的計画法(DP)では、各石iについて、最大K個前の石から最小コストを探す必要があります。この場合、各状態の計算にO(K)かかるため、全体でO(NK)の時間計算量となり、NとKが最大10^6になる制約ではTLE(時間制限超過)になります。

そこで、スライド最小値の考え方を利用します。DP配列を計算する際に、直近K個の範囲内で最小値を効率的に管理することで、各ステップを定数時間で処理できるようにします。

アルゴリズム

1. DP配列を用意し、dp[0] = A[0]（スタート地点のコスト）で初期化します
2. デック（両端キュー）を使用して、直近K個の範囲内で最小のDP値を持つインデックスを管理します
3. 各石i (1 ≤ i < N)について：
   • デックの先頭が範囲外（i-K未満）になったら削除
   • dp[i] = dp[デック先頭] + A[i] で計算
   • デックの末尾から、dp[i]以上の値を持つインデックスを削除してからiを追加
4. 最終的にdp[N-1]が最小コストとなります

デックには常に「単調増加」になるようにインデックスを保持します。これにより、常に範囲内の最小値が先頭に来るようになります。

計算量

• 時間計算量: \(O(N)\) - 各石はデックに最大1回追加され、1回削除されるため
• 空間計算量: \(O(N)\) - DP配列とデックのサイズがNに比例するため

実装のポイント

• デックにはインデックスを格納し、実際の値はDP配列から参照します

• 範囲外のチェックは dq[0] < i - k で行います（i-k未満のインデックスを削除）

• デックの管理では「新しい値を追加する前に、それより大きい値を末尾から削除」することで単調性を保ちます

• 0-indexedで実装しているため、最終的な答えはdp[n-1]になります

  ソースコード

import sys
from collections import deque

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    dp = [0] * n
    dq = deque()
    dq.append(0)
    dp[0] = A[0]
    
    for i in range(1, n):
        while dq and dq[0] < i - k:
            dq.popleft()
            
        dp[i] = dp[dq[0]] + A[i]
        
        while dq and dp[i] <= dp[dq[-1]]:
            dq.pop()
        dq.append(i)
        
    print(dp[n-1])

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。