概要

各石にコスト \(A_i\) があり、最大 \(K\) 個先まで進めるとき、石 \(1\) から石 \(N\) まで到達する累計コストの最小値を求める問題です。

考察

石 \(i\) に到達する直前は、必ずどこかの石 \(j\)（\(i-K \le j \le i-1\)）からジャンプしてきます。したがって「石 \(i\) までの最小コスト」は、直前候補の最小値を使って更新できます。

• \(dp[i]\) を「石 \(i\) に着地したときの累計コスト最小値」とすると、 $\( dp[i] = A_i + \min\{dp[j] \mid i-K \le j \le i-1\} \)$ となります（範囲外は無視）。

素朴にこの式をそのまま計算すると、各 \(i\) について最大 \(K\) 個の候補を見て最小を取るため \(O(NK)\) です。
制約は \(N \le 10^6\) なので、例えば \(K \approx N\) だと \(10^{12}\) 回規模になり、確実に TLE します。

そこで必要なのは、各 \(i\) で求める $\( \min\{dp[i-K], dp[i-K+1], \ldots, dp[i-1]\} \)\( という「長さ \)K$ のスライドする区間の最小値」を高速に更新することです。

アルゴリズム

単調キュー（Monotone Queue） を使って「直近 \(K\) 個の \(dp\) の最小値」を \(O(1)\)（償却）で取得します。

手順

1. \(dp[1]=A_1\)、以降 \(dp[i]=A_i+\text{(直前 \)K\( 個の }dp\text{の最小)}\) を計算する。
2. deque（両端キュー）に「最小値候補となる添字」を入れて管理する。
   • deque の中では \(dp\) 値が単調増加 になるように保つ
     （先頭が常に最小の \(dp\) を持つ添字になる）。
3. 各 \(i\) について：
   • 範囲外（\(< i-K\)）の添字を先頭から取り除く
   • 先頭の添字が「区間内の最小 \(dp\)」なので、それを使って $\( dp[i] = A_i + dp[\text{deque[0]}] \)$
   • 新しい \(dp[i]\) を追加するとき、末尾から「\(dp\) が \(dp[i]\) 以上」のものは不要になるので削除し、最後に \(i\) を追加する

なぜ末尾を削除してよいか

末尾の添字 \(t\) が \(dp[t] \ge dp[i]\) のとき、将来のどの区間でも（\(t\) と \(i\) の両方が候補に残る状況では）\(t\) より \(i\) の方が常に同じか安いので、\(t\) は最小候補になり得ません。そのため捨てても正解に影響しません。

計算量

• 時間計算量: \(O(N)\)
  （各添字は deque に高々1回入り、高々1回出るため、全体で償却 \(O(N)\)）
• 空間計算量: \(O(N)\)
  （\(dp\) 配列が \(N\)、deque は最大でも \(N\)）

実装のポイント

• \(N=10^6\) なので、Python では入出力がボトルネックになりやすいです。コードでは sys.stdin.buffer.read() + 自前パーサで高速化しています。

• dq には「添字」を入れ、比較は dp[添字] で行います。

• 範囲外削除は while dq[0] < i-K: dq.popleft() のように行い、常に deque 先頭が「使える最小候補」になるようにします。

• コストは最大で \(10^9 \times 10^6\) 規模になり得ますが、Python の int は任意精度なのでオーバーフローの心配はありません。

  ソースコード

import sys
from collections import deque

def main():
    data = memoryview(sys.stdin.buffer.read())
    ndata = len(data)
    idx = 0

    def read_int():
        nonlocal idx
        while idx < ndata and data[idx] <= 32:
            idx += 1
        num = 0
        while idx < ndata and data[idx] > 32:
            num = num * 10 + (data[idx] - 48)
            idx += 1
        return num

    N = read_int()
    K = read_int()
    dp = [0] * N
    for i in range(N):
        dp[i] = read_int()

    dq = deque([0])  # indices with increasing dp
    for i in range(1, N):
        limit = i - K
        while dq[0] < limit:
            dq.popleft()
        dp[i] = dp[i] + dp[dq[0]]
        while dq and dp[dq[-1]] >= dp[i]:
            dq.pop()
        dq.append(i)

    sys.stdout.write(str(dp[-1]))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。