概要

各石にあるコイン（負もあり）を取りながら、最大 \(K\) 個先まで右にジャンプして石 \(N\) に到達するとき、獲得コイン合計の最大値を求める問題です。

考察

石は右方向にしか進めず同じ石に二度立たないので、「石 \(i\) に到達した時点での最大獲得枚数」を考える動的計画法（DP）が自然です。

石 \(i\) に来る直前は、石 \(i-K, i-K+1, \ldots, i-1\) のいずれか（存在する範囲）です。よって - 石 \(i\) に到達したときの最大値は、「到達可能な直前の石のDP最大値 + \(A_i\)」になります。

素朴にこれを実装すると、各 \(i\) について最大 \(K\) 個を見て最大を取るため - \(O(NK)\) となり、\(N \le 2 \times 10^5\) では最悪 \(4 \times 10^{10}\) 回程度になって TLE します。

そこで必要なのは、各 \(i\) で求めたい - 区間 \([i-K,\, i-1]\) における \(dp\) の最大値 を高速に更新・取得することです。これは「スライディングウィンドウ最大値」問題で、単調キュー（deque）で \(O(1)\) 償却で扱えます。

アルゴリズム

1. DPの定義

\(dp[i]\) を「石 \((i+1)\)（0-indexで i）に到達してその石のコインも獲得した後の、獲得コイン合計の最大値」とします。

• 初期値：最初は石1に立っているので \(dp[0] = A_1\)
• 遷移（\(i \ge 1\)）：
  • 石 \(i\) に来られる直前の石は \(i-K \sim i-1\)
  • よって
    \(dp[i] = A_{i+1} + \max\{ dp[j] \mid i-K \le j \le i-1 \}\)
    （ただし \(j \ge 0\) の範囲）

2. 単調キューで区間最大を管理

deque に「\(dp\) が大きい順（単調減少）」になるようにインデックスを保持します。

各 \(i=1..N-1\) について次を行います：

1. 範囲外の削除
   deque 先頭が \(i-K\) より小さい（=もう \([i-K, i-1]\) に入らない）なら先頭から取り除く。
2. 最大値で遷移
   deque 先頭は常に区間内の \(dp\) 最大のインデックスなので
   \(dp[i] = A[i] + dp[deque[0]]\)
3. 単調性の維持
   新しい \(dp[i]\) が後ろの要素以上なら、後ろは今後最大になり得ないので後ろから削除し、最後に \(i\) を追加。

これにより、各インデックスは deque に高々1回入って高々1回出るため全体 \(O(N)\) で処理できます。

（簡単なイメージ例）
「次にどこへ飛ぶか」は毎回「直前 \(K\) 個の中で最も得な状態（dpが最大）」から来るのが最適なので、その“最も得な候補”をdequeで常に先頭に置いておきます。

計算量

• 時間計算量: \(O(N)\)（dequeへの出し入れは各要素につき高々1回ずつ）
• 空間計算量: \(O(N)\)（\(dp\) 配列と deque）

実装のポイント

• インデックスを 0-index で統一すると実装が簡潔になります（コードもそうなっています）。

• deque から範囲外を消す条件は q[0] < i - K です（到達可能な直前は \(i-K\) 以上）。

• 単調性維持では dp[q[-1]] <= dp[i] の間 pop します。<= にしておくと同値のとき古い方を捨てられ、deque が不要に長くなりません。

• \(A_i\) は負の場合もあるため、「できるだけ多くの石を踏む」などの貪欲は成立せず、DPが必要です。

  ソースコード

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    dp = [0] * N
    dp[0] = A[0]
    
    q = deque([0])  # indices with dp in decreasing order
    
    for i in range(1, N):
        while q and q[0] < i - K:
            q.popleft()
        dp[i] = A[i] + dp[q[0]]
        while q and dp[q[-1]] <= dp[i]:
            q.pop()
        q.append(i)
    
    print(dp[-1])

if __name__ == "__main__":
    main()

---

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