概要

連続する \(K\) 本の木から収穫できる果物の合計を最大化する問題です。スライディングウィンドウ（尺取り法）を使って効率的に解くことができます。

考察

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

最も単純な方法は、すべての連続する \(K\) 本の区間について合計を計算することです。

• 開始位置は \(1, 2, \ldots, N-K+1\) の \(N-K+1\) 通り
• 各区間の合計計算に \(O(K)\) かかる
• 全体で \(O((N-K+1) \times K) = O(NK)\) となり、\(N = 2 \times 10^5\) の場合は最大 \(10^{10}\) 程度の計算になりTLEします

重要な気づき

連続する区間を1つずらすとき、区間の合計値はどう変化するでしょうか？

例えば \(N = 5, K = 3\) で配列が \([2, 5, 3, 8, 1]\) の場合： - 区間 \([1, 3]\)：\(2 + 5 + 3 = 10\) - 区間 \([2, 4]\)：\(5 + 3 + 8 = 16\)

区間を1つ右にずらすと： - 左端の要素（\(A_1 = 2\)）が抜ける - 右端に新しい要素（\(A_4 = 8\)）が入る

つまり、前の区間の合計から1つ引いて1つ足すだけで、次の区間の合計が \(O(1)\) で計算できます！

アルゴリズム

スライディングウィンドウ（Sliding Window） を使います。

1. まず最初の \(K\) 本の木（\(A_0\) から \(A_{K-1}\)）の合計を計算し、これを current_sum とする
2. max_sum を current_sum で初期化
3. 区間を1つずつ右にずらしながら、以下を繰り返す：
   • 新しく入る要素 \(A_i\) を足す
   • 抜ける要素 \(A_{i-K}\) を引く
   • max_sum を更新

例: N=5, K=3, A=[2, 5, 3, 8, 1]

初期: [2, 5, 3] → current_sum = 10, max_sum = 10
i=3:  [5, 3, 8] → current_sum = 10 - 2 + 8 = 16, max_sum = 16
i=4:  [3, 8, 1] → current_sum = 16 - 5 + 1 = 12, max_sum = 16

答え: 16

計算量

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

  • 最初の \(K\) 要素の合計計算: \(O(K)\)
  • ウィンドウをスライドさせる処理: \(O(N - K)\) 回、各回 \(O(1)\)
  • 合計: \(O(K) + O(N - K) = O(N)\)

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

  • 配列 \(A\) を保持するのに \(O(N)\)
  • その他の変数は \(O(1)\)

実装のポイント

1. 初期区間の合計計算: Pythonでは sum(A[:K]) でスライスを使って簡潔に書ける

2. インデックスの管理:

   • 新しく追加する要素は \(A[i]\)（\(i\) は \(K\) から \(N-1\) まで）
   • 削除する要素は \(A[i-K]\)

3. オーバーフロー対策: \(A_i\) が最大 \(10^9\)、\(K\) が最大 \(2 \times 10^5\) なので、合計は最大 \(2 \times 10^{14}\) 程度。Pythonは多倍長整数なので問題ないが、他の言語では64ビット整数を使う必要がある

   ソースコード

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # 最初のK本の木の果物の合計を計算
    current_sum = sum(A[:K])
    max_sum = current_sum
    
    # スライディングウィンドウで最大値を探す
    for i in range(K, N):
        # 新しい木を追加し、古い木を除去
        current_sum += A[i] - A[i - K]
        max_sum = max(max_sum, current_sum)
    
    print(max_sum)

solve()

---

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