概要

石に書かれたコストを最小にして、飛び石を跳んで川を渡る最適な経路を求める問題です。

考察

この問題は典型的な「動的計画法（DP）」で解くことができます。
石 \(i\) に到達する最小コストを \(dp[i]\) とします。
石 \(i\) には、石 \(i-K\) から石 \(i-1\) のどれかからジャンプして到達できるので、次のように更新できます：

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

しかし、この素朴なDPでは、各 \(i\) に対して最大 \(K\) 個の候補を調べる必要があり、最悪ケースで時間計算量が \(O(NK)\) になってしまいます。
制約より、\(N\) や \(K\) が最大 \(10^6\) になり得るので、全体で \(10^{12}\) となり、現実的な時間内に解けません（TLE）。

そこで、区間の最小値を高速に取得・更新できるデータ構造「スライディングウィンドウ最小値（deque を用いた実装）」を使うことで、この問題を効率的に解きます。
具体的には、ある範囲内の \(dp[j]\) の最小値を常に deque に保つように管理することで、各ステップで \(O(1)\) で最小値を取得できます。

アルゴリズム

1. DP配列 dp を用意し、初期値として dp[0] = A[0] を設定します（0-indexed）。
2. 最小値を管理する deque を用意し、最初は index 0 を入れておきます。
3. 各石 \(i = 1\) から \(N-1\) について：
   • deque の先頭が範囲 \([i-K, i-1]\) 外なら取り除く。
   • dp[i] = dp[deque先頭] + A[i] で更新。
   • deque の末尾から、dp[i] 以上になる無駄な要素を取り除き、i を追加。
4. 最後に dp[N-1] が答え。

このように deque を使うことで、区間最小値の取得と更新を効率化しています。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

各要素は deque に高々1回追加・削除されるため、全体で線形時間で処理できます。

実装のポイント

• 石の番号は1-indexedだが、内部では0-indexedで扱うと実装がシンプルになります。

• deque にはインデックスを保持し、対応する dp の値を比較して管理します。

• dp[i] を計算した後、deque に追加する前に、末尾から無駄な要素を削除する処理が必要です。

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # dp[i] := 石 i に到達するための最小コスト
    # 石の番号は 0-indexed で扱う（元の問題は 1-indexed）
    dp = [float('inf')] * N
    dp[0] = A[0]
    
    # 最小コストを保持する deque (sliding window minimum)
    dq = deque()
    dq.append(0)
    
    for i in range(1, N):
        # 範囲外のインデックスを削除
        while dq and dq[0] < i - K:
            dq.popleft()
        
        # 現在の最小コストを使って dp[i] を更新
        dp[i] = dp[dq[0]] + A[i]
        
        # dp[i] を deque に追加するために、無駄な要素を削除
        while dq and dp[dq[-1]] >= dp[i]:
            dq.pop()
        dq.append(i)
    
    print(dp[N - 1])

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。