概要

この問題は、一列に並んだ \(N\) 本の木から果物を収穫する際、ある木で収穫するとその後 \(K\) 本の木では収穫できないという制約の下で、収穫できる果物の合計を最大化する問題です。

考察

各木において、高橋君が取れる行動は「その木で収穫する」か「その木では収穫しない」かの 2 択です。

• 収穫する場合: 最後に収穫した木から \(K\) 本以上の間隔を空ける必要があります。つまり、 \(i\) 番目の木で収穫する場合、その前に収穫できたのは \(i-K-1\) 番目以前の木となります。
• 収穫しない場合: \(i-1\) 番目の木までの収穫状況をそのまま引き継ぎます。

このように、「現在の状態がそれより前の状態に基づいて決まる」という構造をしているため、動的計画法 (DP) を用いて効率的に解くことができます。

\(N\) が最大 \(2 \times 10^5\) と大きいため、二重ループによる \(O(N^2)\) の解法では間に合いませんが、今回の制約であれば直前の状態を参照するだけの \(O(N)\) の解法で十分に間に合います。

アルゴリズム

以下の通り DP テーブルを定義します。

• dp[i] : \(i\) 番目までの木を考慮したときの、収穫できる果物の合計個数の最大値

\(i = 1\) から \(N\) まで順番に、以下の 2 つのパターンの大きい方を dp[i] とします。

1. \(i\) 番目の木で収穫しない場合

   • \(i-1\) 番目までの最大値と同じになります。
   • 式: dp[i-1]

2. \(i\) 番目の木で収穫する場合

   • \(i\) 番目の木の果物 \(A_i\) に加え、最後に収穫可能だった \(i-K-1\) 番目時点での最大値を足します。
   • \(i-K-1 \leq 0\) の場合は、それ以前に収穫した木はないものとして \(A_i\) のみを加算します。
   • 式: A[i-1] + dp[max(0, i-K-1)]

最終的な答えは dp[N] となります。

計算量

• 時間計算量: \(O(N)\)
  • 木の数 \(N\) に対して、1 回のループで DP テーブルを埋めることができるため、非常に高速です。
• 空間計算量: \(O(N)\)
  • 長さ \(N+1\) の DP テーブルを保持するためのメモリが必要です。

実装のポイント

• インデックスの調整: プログラミング言語の配列は通常 0 始まり（0-indexed）ですが、DP の遷移を考えるときは「\(i\) 番目までの結果」として 1 始まりで管理すると境界条件（\(i=0\) のときなど）が扱いやすくなります。

• 大きな入力の処理: Python の場合、input() を繰り返すよりも sys.stdin.read().split() を使用して一括で読み込む方が実行時間を短縮できる場合があります。

• 最大値の更新: max(val_skip, val_pick) を用いて、常にその時点での最適解を保持するようにします。

  ソースコード

import sys

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 番目までの木を考慮したときの収穫できる果物の合計個数の最大値
    # dp[0] = 0 (木が0本のときは0)
    dp = [0] * (N + 1)
    
    for i in range(1, N + 1):
        # i 番目の木 (インデックス A[i-1]) を収穫しない場合
        # 直前の状態 dp[i-1] を引き継ぐ
        val_skip = dp[i-1]
        
        # i 番目の木 (インデックス A[i-1]) を収穫する場合
        # 直後の K 本が収穫不可ということは、直前の K 本も収穫不可であったはず
        # つまり、最後に収穫できた可能性があるのは i-K-1 番目以前の木
        prev_idx = i - K - 1
        val_pick = A[i-1]
        if prev_idx > 0:
            val_pick += dp[prev_idx]
        
        # 収穫する場合としない場合の大きい方を採用する
        if val_skip > val_pick:
            dp[i] = val_skip
        else:
            dp[i] = val_pick
            
    # 全体の最大値を出力する
    print(dp[N])

if __name__ == '__main__':
    solve()

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