概要

石渡りゲームでは、一列に並んだ石をジャンプで移動しながらコインを集め、石Nに到達するまでの獲得コインの最大値を求める問題です。

考察

各石iに到達する最大コイン数をdp[i]とすると、dp[i]は「1つ前のK個の石のdp値の最大値 + A[i]」で計算できます。しかし、単純に各石について前K個を調べると計算量がO(NK)となり、NとKが最大20万になるため最悪ケースで400億回の計算が必要になり、時間制限に間に合いません。そこで、スライディングウィンドウ最大値を効率的に求めるデータ構造が必要です。

アルゴリズム

動的計画法と両端キューを用いたスライディングウィンドウ最大値の手法を使用します。 1. dp[0] = A[0]で初期化（最初の石のコイン） 2. 両端キュー(dq)を用意し、インデックス0を追加 3. i=1からN-1まで順に処理: - ウィンドウ外（i-Kより前）のインデックスをキューから削除 - dp[i] = dp[dqの先頭] + A[i] を計算 - キュー末尾のdp値が現在のdp[i]以下なら削除（不要な値を排除） - 現在のインデックスiをキュー末尾に追加

両端キューは常にdp値が単調減少（末尾が最小）になるよう維持され、ウィンドウ内の最大値を持つインデックスが先頭に来ます。これにより各ステップで最大値をO(1)で取得できます。

計算量

• 時間計算量: \(O(N)\)（各インデックスはキューに最大1回追加・削除される）
• 空間計算量: \(O(N)\)（dp配列とキューに使用）

実装のポイント

• 両端キューにはインデックスを格納し、dp値の比較で不要なインデックスを削除

• キュー操作ではウィンドウ範囲外のインデックスを確実に削除

• 最初の石（インデックス0）は必ずキューに追加されるよう初期化

• 負のコインも考慮した実装が必要

  ソースコード

import collections

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

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。