概要

\(N\) 個の石を一列に並んだ川で、1 度に最大 \(K\) 個先まで跳び移りながら、石の上にあるコインを回収して合計を最大化する問題です。この問題は動的計画法（DP）で解くことができますが、素朴な実装では間に合わないため、スライディングウィンドウ最大値という手法を用いて高速化します。

考察

基本的な動的計画法（DP）

まず、次のような DP を考えます。 - \(dp[i]\)：石 \(i\) に到達したときに獲得できるコインの合計の最大値

石 \(i\) に到達する直前の状態は、石 \(i-K, i-K+1, \ldots, i-1\) のいずれかです。したがって、遷移式は以下のようになります。 - \(dp[i] = A_i + \max_{i-K \leq j < i} (dp[j])\) - 初期条件：\(dp[1] = A_1\)

計算量の課題

この遷移式に従って各 \(dp[i]\) を計算する場合、各 \(i\) に対して直前 \(K\) 個の要素から最大値を探す必要があります。 - 石の数 \(N\)：最大 \(2 \times 10^5\) - 跳べる距離 \(K\)：最大 \(N-1\)

素直にループで最大値を求めると、全体の計算量は \(O(N \times K)\) となり、最悪ケースで \(O(N^2) \approx 4 \times 10^{10}\) 回の計算が必要です。これは一般的な実行時間制限（2秒）を大幅に超えてしまいます。

高速化のアイデア

「特定の範囲（ウィンドウ）の最大値を効率よく取得する」という課題を解決するために、スライディングウィンドウ最大値というアルゴリズムを使用します。 これは、デック（両端キュー）を用いることで、ウィンドウ内の最大値を \(O(1)\)、全体で \(O(N)\) で求める手法です。

アルゴリズム

スライディングウィンドウ最大値（デック活用）

デックの中には、「将来的に最大値になる可能性がある要素のインデックス」を保持します。具体的には、デック内のインデックスに対応する \(dp\) の値が常に降順（大きい順）になるように維持します。

1. 古い要素の削除: デックの先頭にあるインデックスが、現在の石から \(K\) 以上離れている（\(j < i-K\)）場合、そのインデックスをデックから取り除きます。
2. 最大値の取得: デックの先頭にあるインデックスは、範囲 \([i-K, i-1]\) の中で \(dp\) の値が最大であるものを指しています。これを使って \(dp[i] = A_i + dp[\text{先頭}]\) を計算します。
3. 新しい要素の追加: \(dp[i]\) をデックに追加する際、デックの末尾にある要素のうち、 \(dp[i]\) 以下の値を持つインデックスをすべて取り除きます。その後、 \(i\) を末尾に追加します。
   • なぜなら、より新しくて（右側にあり）かつ値が大きい（または等しい） \(dp[i]\) が現れた以上、それより古くて値が小さい要素が今後最大値として選ばれることはないからです。

この操作により、各要素はデックに「1回入り、1回出る」だけになるため、全体の計算量が \(O(N)\) に抑えられます。

計算量

• 時間計算量: \(O(N)\)
  • 各石についてデックへの追加・削除操作は高々1回ずつであるため、全体で \(N\) に比例する時間で終わります。
• 空間計算量: \(O(N)\)
  • \(dp\) 配列およびデックのサイズは最大で \(N\) です。

実装のポイント

• デックの利用: Python では collections.deque を使うことで、先頭と末尾の両方からの削除・追加を効率的に行えます。

• インデックスの管理: 石の番号は 1 から始まりますが、プログラム内では 0-indexed（0番目〜 \(N-1\) 番目）として扱うと実装がスムーズです。

• 初期値: 最初の石（石 1）は必ず通るため、dp[0] = A[0] からスタートします。

  ソースコード

import sys
from collections import deque

def solve():
    # 標準入力からすべてのデータを読み込み、スペースや改行で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 石の数, K: 一度に跳べる最大距離
    N = int(input_data[0])
    K = int(input_data[1])
    # A: 各石の上にあるコインの枚数 (0-indexedで管理)
    A = list(map(int, input_data[2:]))
    
    # dp[i] は石 i+1 に到達したときに獲得できるコインの合計の最大値を保持します
    # 石 1 は A[0], 石 N は A[N-1] に対応します
    dp = [0] * N
    dp[0] = A[0]
    
    # スライディングウィンドウ内の最大値を効率的に取得するために
    # デック（両端キュー）を用いたスライディングウィンドウ最大値のアルゴリズムを使用します。
    # dq には dp のインデックスを格納し、dp[dq[j]] が降順になるように維持します。
    dq = deque([0])
    
    for i in range(1, N):
        # 現在の石 i に到達可能な範囲は [i-K, i-1] です。
        # デックの先頭にあるインデックスがこの範囲外（i-K 未満）になった場合、取り除きます。
        if dq and dq[0] < i - K:
            dq.popleft()
        
        # デックの先頭にあるインデックスが、範囲内 [i-K, i-1] で dp の値が最大となるインデックスです。
        dp[i] = A[i] + dp[dq[0]]
        
        # 新しく計算した dp[i] をデックに追加します。
        # 降順を維持するため、dp[i] 以下の値を持つ既存のインデックスを末尾から取り除きます。
        while dq and dp[dq[-1]] <= dp[i]:
            dq.pop()
        
        dq.append(i)
        
    # 石 N (インデックス N-1) に到達したときの最大値を出力します
    print(dp[N-1])

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。