概要

一列に並んだ木から果物を収穫する問題で、一度収穫すると次の \(K\) 本の木では収穫できないという制約の下で、収穫量を最大化する動的計画法（DP）の問題です。

考察

重要な気づき

• \(i\) 番目の木で収穫した場合、次に収穫できるのは \(i + K + 1\) 番目の木以降です
• 逆に言えば、\(i\) 番目の木で収穫するためには、直前の収穫は \(i - K - 1\) 番目以前でなければなりません

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

各木について「収穫する/しない」の2択があるので、全探索すると \(O(2^N)\) 通りになります。\(N \leq 2 \times 10^5\) では到底間に合いません。

解決方針

動的計画法を使います。「\(i\) 番目の木で収穫したときの最大収穫量」を \(dp[i]\) として定義すると、状態遷移は以下のようになります：

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

ただし、各 \(i\) について \(j\) を全探索すると \(O(N^2)\) になってしまいます。

高速化のポイント

「\(dp[0]\) から \(dp[i]\) までの最大値」を \(max\_dp[i]\) として別途管理すれば、\(\max_{0 \leq j \leq i-K-1} dp[j]\) は \(max\_dp[i-K-1]\) として \(O(1)\) で取得できます。

アルゴリズム

1. \(dp[i]\)：\(i\) 番目の木で収穫したときの最大収穫量
2. \(max\_dp[i]\)：\(dp[0], dp[1], \ldots, dp[i]\) の最大値

状態遷移： - \(i \leq K\) のとき：\(i\) 番目より前に収穫可能な木がないので、\(dp[i] = A_i\) - \(i > K\) のとき：\(dp[i] = A_i + max\_dp[i - K - 1]\) - \(i - K - 1\) 番目以前で収穫した最大値に \(A_i\) を加える

具体例 (\(N = 5, K = 1, A = [3, 1, 4, 1, 5]\))：

\(i\)	\(A_i\)	\(dp[i]\)	\(max\_dp[i]\)	説明
0	3	3	3	最初の木
1	1	1	3	\(K=1\) なので前の木を参照できない
2	4	4 + 3 = 7	7	\(max\_dp[0] = 3\) を利用
3	1	1 + 3 = 4	7	\(max\_dp[1] = 3\) を利用
4	5	5 + 7 = 12	12	\(max\_dp[2] = 7\) を利用

答えは \(max\_dp[4] = 12\)（木0と木2と木4から収穫）

計算量

• 時間計算量: \(O(N)\) — 各木について定数時間の処理
• 空間計算量: \(O(N)\) — \(dp\) 配列と \(max\_dp\) 配列

実装のポイント

• \(i - K - 1 < 0\) のときは、それ以前に収穫した木がない（または収穫していない）状態なので、\(dp[i] = A_i\) となります

• 最終的な答えは \(max\_dp[N-1]\) です。これは「どこかの木で最後に収穫した場合の最大値」を表します

• \(max\_dp\) を更新するタイミングに注意：\(dp[i]\) を確定させてから \(max\_dp[i]\) を更新します

  ソースコード

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # dp[i] = i番目の木まで見たときに収穫できる果物の最大個数
    # ただし、i番目の木で収穫した場合とそうでない場合を考慮
    
    # dp[i] = i番目の木で収穫した場合の、そこまでの最大収穫量
    # i番目の木で収穫するには、i-K-1番目以前の木で最後に収穫している必要がある
    
    dp = [0] * N
    
    # max_dp[i] = dp[0]からdp[i]までの最大値
    # これにより、dp[j] (j <= i-K-1) の最大値を O(1) で取得できる
    
    for i in range(N):
        # i番目の木で収穫する場合
        if i <= K:
            # i-K-1 < 0 なので、これより前に収穫した木はない（または収穫していない）
            dp[i] = A[i]
        else:
            # i-K-1番目以前の木で最後に収穫した場合の最大値 + A[i]
            # または、一度も収穫していない状態から収穫する場合は A[i]
            dp[i] = A[i]
    
    # max_dp[i] = max(dp[0], dp[1], ..., dp[i])
    max_dp = [0] * N
    max_dp[0] = dp[0]
    
    for i in range(1, N):
        # i番目の木で収穫する場合、i-K-1番目以前で収穫した最大値を利用
        if i - K - 1 >= 0:
            dp[i] = max(dp[i], max_dp[i - K - 1] + A[i])
        
        max_dp[i] = max(max_dp[i - 1], dp[i])
    
    print(max_dp[N - 1])

solve()

---

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