概要

各木で「収穫する／しない」を選ぶとき、収穫したら次の \(K\) 本は収穫できないという制約のもとで、収穫できる果物の合計の最大値を求めます。

考察

この問題は「隣接（あるいは一定距離以内）の要素を同時に選べないときの最大和」という典型です。

• ある木 \(i\) を収穫すると、次の \(K\) 本（\(i+1\) 〜 \(i+K\)）は必ず収穫できません。
• つまり、木 \(i\) を選ぶなら、その直前に選べる木は高々 \(i-(K+1)\) 番目までです。

素朴に「次に収穫できる木を探しながら全探索」すると、選択肢が指数的に増えてしまい \(N \le 2\times 10^5\) では間に合いません（TLE）。
そこで、「最初の \(i\) 本まで見たときの最適値」を使う動的計画法（DP）により、各 \(i\) での最適解を \(O(1)\) で更新していきます。

具体例として \(K=2\) のとき、木 \(i\) を収穫したなら木 \(i-1, i-2\) は収穫できないので、組み合わせるなら「木 \(i-3\) 以前での最適解 + \(A_i\)」になります。

アルゴリズム

DP を次のように定義します。

• \(dp[i]\): 「先頭から \(i\) 本目までの木（\(1 \sim i\)）を見たときに収穫できる果物の最大個数」

このとき、\(i\) 本目の木について選択は 2 通りです。

1. 収穫しない
   何も変わらないので \(dp[i-1]\)。
2. 収穫する
   直前に収穫できるのは高々 \(i-(K+1)\) 本目までなので、
   \(dp[i-(K+1)] + A_i\)（ただし \(i-(K+1) \le 0\) のときは \(dp[0]=0\) とみなす）

よって遷移は

• \(t = \max(0,\, i-K-1)\)
• \(dp[i] = \max\bigl(dp[i-1],\ dp[t] + A_i\bigr)\)

となります。
これを \(i=1\) から順に計算すれば答えは \(dp[N]\) です。

（コードでは配列が 0-indexed なので、\(A_i\) は A[i-1] として参照しています。）

計算量

• 時間計算量: \(O(N)\)（各 \(i\) で定数時間の更新）
• 空間計算量: \(O(N)\)（\(dp\) 配列）

実装のポイント

• \(t = i-K-1\) が負になる場合があるので、max(0, t) のように丸めて \(dp[0]=0\) を使うのが重要です。

• \(A\) は 0-indexed、\(dp\) は「\(i\) 本まで」を表す 1-indexed風の定義（長さ \(N+1\)）にすると、遷移が書きやすくなります。

• \(N\) が大きいので、入力は sys.stdin.readline を使うと安全です。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [0] * (N + 1)  # dp[i]: max fruits from first i trees

    for i in range(1, N + 1):
        take_prev = i - K - 1
        if take_prev < 0:
            take_prev = 0
        dp[i] = max(dp[i - 1], dp[take_prev] + A[i - 1])

    print(dp[N])

if __name__ == "__main__":
    main()

---

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