概要

石1から石Nまで、最大K歩のジャンプを繰り返して移動するとき、獲得できるコインの最大枚数を求める動的計画法（DP）の問題です。スライド最大値を用いて効率的に解きます。

考察

素朴なDPアプローチ

まず、動的計画法で解くことを考えます。

\(dp[i]\) を「石 \(i\) に到達したときの最大コイン獲得数」と定義すると、以下の漸化式が成り立ちます：

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

つまり、石 \(i\) には石 \(i-K\) から石 \(i-1\) のいずれかからジャンプして到達できるので、その中で \(dp\) 値が最大のものを選びます。

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

各 \(dp[i]\) の計算で最大 \(K\) 個の候補を調べるため、全体で \(O(NK)\) の計算量になります。\(N, K\) が最大 \(2 \times 10^5\) のとき、最悪 \(4 \times 10^{10}\) 回の演算が必要となり、TLE（時間超過）してしまいます。

解決方法：スライド最大値

「直前 \(K\) 個の要素の中での最大値」を効率的に求める必要があります。これはスライド最大値（別名：単調減少デック、モノトニックデック）というテクニックで \(O(1)\)（ならし計算量）で求められます。

アルゴリズム

単調減少デックの仕組み

デック（両端キュー）を用いて、以下の性質を常に維持します： - デック内の要素はインデックスの昇順に並んでいる - デック内の要素は値の降順（単調減少）に並んでいる

この性質により、デックの先頭には常に「現在の範囲内での最大値」が入っています。

処理の流れ

1. 初期化: \(dp[0] = A[0]\)（石1のコインを獲得）
2. 各石 \(i\) について (\(i = 1, 2, \ldots, N-1\))：
   • 範囲外の削除: デックの先頭から、インデックスが \(i - K\) 未満のものを削除
   • 最大値の取得: デックの先頭が範囲内の最大値なので、\(dp[i] = (\text{先頭の値}) + A[i]\)
   • 単調性の維持: デックの末尾から、\(dp[i]\) 以下の値を削除してから \(dp[i]\) を追加

具体例

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

\(i\)	参照範囲	デックの状態	\(dp[i]\)
0	-	[(3, 0)]	3
1	[0]	[(3, 0), (1, 1)]	3 + (-2) = 1
2	[0,1]	[(4, 2)]	3 + 1 = 4
3	[1,2]	[(8, 3)]	4 + 4 = 8
4	[2,3]	[(8, 3), (7, 4)]	8 + (-1) = 7

答え: \(dp[4] = 7\)

計算量

• 時間計算量: \(O(N)\)
  • 各要素はデックに1回追加され、1回削除されるため
• 空間計算量: \(O(N)\)
  • \(dp\) 配列とデックの両方で最大 \(O(N)\) の要素を保持

実装のポイント

• デックには (値, インデックス) のペアを格納することで、範囲外判定と最大値取得の両方に対応

• 単調性を維持する際は <= で比較し、同じ値なら新しい方を残す（どちらでも正解だが、統一すること）

• 0-indexedと1-indexedの混同に注意（このコードは0-indexed）

  ソースコード

from collections import deque

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # dp[i] = i番目の石に到達したときの最大コイン数
    # dp[i] = max(dp[j] for j in range(max(0, i-K), i)) + A[i]
    
    # スライド最大値を使って効率化
    # dequeには (値, インデックス) を格納
    
    dp = [0] * N
    dp[0] = A[0]
    
    # 単調減少キュー（モノトニックデック）を使用
    dq = deque()
    dq.append((dp[0], 0))
    
    for i in range(1, N):
        # 範囲外になったインデックスを削除
        while dq and dq[0][1] < i - K:
            dq.popleft()
        
        # 現在の最大値を取得
        dp[i] = dq[0][0] + A[i]
        
        # 単調減少を維持するため、現在の値以下のものを後ろから削除
        while dq and dq[-1][0] <= dp[i]:
            dq.pop()
        
        dq.append((dp[i], i))
    
    print(dp[N - 1])

solve()

---

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