概要

一列に並んだ果樹から、ある木で収穫するとその後 \(K\) 本の木では収穫できない制約下で、得られる果物の最大個数を求める問題。

考察

この問題は、一見すると「どの木で収穫するか」を全探索すれば解けそうに思えるが、木の本数 \(N\) が最大で \(2 \times 10^5\) であるため、指数時間の探索は不可能です。

重要な観察は、「\(i\) 番目の木で収穫する」という選択は、それ以前のある木で最後に収穫した位置に依存するということです。具体的には、\(i\) 番目の木で収穫するためには、前回の収穫が \(i - K - 1\) 番目以前に行われている必要があります。

このような「ある条件を満たす中での最大値を求める」問題に対しては、動的計画法（DP）が有効です。

DPの定義

• \(dp[i]\) := \(i\) 番目の木で初めて収穫するときの、それまでの収穫果物の最大個数

このとき、遷移は以下のようになります： $\( dp[i] = \max_{j \leq i - K - 1} dp[j] + A[i] \)$

しかし、このままでは各 \(i\) に対して最大で \(O(N)\) の計算が必要になり、全体で \(O(N^2)\) となり間に合いません。

計算量の最適化

必要なのは「過去の \(dp[j]\) の最大値」だけなので、事前に累積最大値を管理しておくことで高速化できます。

• \(prefix\_max[i] = \max(dp[0], dp[1], \dots, dp[i])\)

これにより、\(dp[i]\) を求める際に毎回ループせずとも、\(prefix\_max[i - K - 1]\) を参照するだけで済みます。これで計算量が \(O(N)\) になります。

アルゴリズム

1. 入力を読み込む（高速化のため sys.stdin.read を使用）。
2. \(dp[i]\) を「\(i\) 番目の木で初めて収穫するときの最大値」として更新。
3. \(prefix\_max[i]\) を「\(dp[0]\) から \(dp[i]\) までの最大値」として保持。
4. 各 \(i\) に対して、\(dp[i] = (i - K - 1 \geq 0\ ?\ prefix\_max[i - K - 1]\ :\ 0) + A[i]\) で計算。
5. 最終的に \(prefix\_max[N - 1]\) が答え（どの木で終わるか分からないので、全体の最大値）。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 入力が非常に大きいため、sys.stdin.read による高速入力処理を行う。
• 累積最大値テーブルを用いて、遷移の計算を定数時間にする。
• インデックスの境界条件（\(i - K - 1 \geq 0\)）に注意する。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # dp[i] := i番目の木まで見て、i番目の木で収穫する場合の最大値
    # ただし、i-K-1以前で最後に収穫した木をjとすると、j <= i-K-1
    # つまり、dp[i] = max_{j <= i-K-1} dp[j] + A[i]
    
    # 最適化: prefix_max[i] = max(dp[0], dp[1], ..., dp[i])
    # dp[i] = (i-K-1 >= 0 ? prefix_max[i-K-1] : 0) + A[i]

    dp = [0] * N
    prefix_max = [0] * N

    for i in range(N):
        prev_max = 0
        if i - K - 1 >= 0:
            prev_max = prefix_max[i - K - 1]
        dp[i] = prev_max + A[i]
        prefix_max[i] = max(prefix_max[i-1] if i > 0 else 0, dp[i])
    
    print(max(prefix_max))

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。