概要

この問題は、長さ \(N\) の数列の中から、連続する \(K\) 個の要素を選んだときの合計値の最大値を求める問題です。

考察

まず、素朴な方法（愚直な解法）を考えてみましょう。 連続する \(K\) 本の木の選び方は、以下の \(N - K + 1\) 通りあります。 - \(1\) 番目から \(K\) 番目 - \(2\) 番目から \(K+1\) 番目 - … - \(N-K+1\) 番目から \(N\) 番目

それぞれの選び方について合計を計算すると、1つの合計を出すのに \(O(K)\) の時間がかかります。選び方が約 \(N\) 通りあるため、全体の計算量は \(O(NK)\) となります。 今回の制約では \(N, K \leq 2 \times 10^5\) であるため、\(NK\) は最大で \(4 \times 10^{10}\) 程度になり、一般的な制限時間（2秒）以内には終わりません。

そこで、「隣り合う範囲の合計値は、ほとんどの要素が共通している」という点に注目します。

例えば、\(K=3\) で \([A_1, A_2, A_3]\) の合計から \([A_2, A_3, A_4]\) の合計に移るとき、変化しているのは「\(A_1\) が抜けて \(A_4\) が入る」という点だけです。 この性質を利用すると、前の範囲の合計値を使って次の範囲の合計値を高速に求めることができます。

アルゴリズム

この手法は、窓を滑らせるように計算することから「スライディングウィンドウ（尺取り法的な考え方）」と呼ばれます。

1. 最初の窓の合計を計算: まず、最初の \(K\) 個（\(A_1\) から \(A_K\)）の合計を計算し、これを暫定の最大値とします。
2. 窓を右にずらす: 次に、窓を一つずつ右にずらしていきます。
   • 新しい合計 = 現在の合計 - (窓から外れる左端の値) + (新しく窓に入る右端の値)
3. 最大値の更新: 新しく求まった合計値と、これまでの最大値を比較して、大きい方を記録します。
4. 繰り返し: これを最後まで繰り返すことで、すべての範囲の合計を \(O(N)\) でチェックできます。

計算量

• 時間計算量: \(O(N)\)
  • 最初の合計計算に \(O(K)\)、その後の更新（\(N-K\) 回）にそれぞれ \(O(1)\) かかるため、全体で \(O(N)\) となります。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 本の木のデータをリストに格納するために \(O(N)\) のメモリを使用します。

実装のポイント

• 大きな数値: 果物の個数の合計は最大で \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) に達します。Pythonでは整数の大きさに制限がないため問題ありませんが、C++などの言語を使用する場合は long long 型などの 64bit 整数型を使う必要があります。

• 入力の高速化: \(N\) が大きいため、Pythonで input() を何度も呼び出すと遅くなることがあります。sys.stdin.read().split() などを使って一括で読み込むと高速です。

  ソースコード

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_i を整数のリストとして取得します
    # スライスを使用して、確実に N 個の要素のみを対象にします
    a = list(map(int, input_data[2:2+n]))
    
    # 最初の K 本の木の果物の合計を計算します
    current_sum = sum(a[:k])
    max_sum = current_sum
    
    # スライディングウィンドウを用いて、連続する K 本の木の合計の最大値を求めます
    # i はウィンドウから外れる要素のインデックスです
    # i + k は新しくウィンドウに入る要素のインデックスになります
    for i in range(n - k):
        # ウィンドウを右に1つずらす：左端の要素を引き、右端の次の要素を足します
        current_sum = current_sum - a[i] + a[i + k]
        # これまでの最大値と比較して更新します
        if current_sum > max_sum:
            max_sum = current_sum
            
    # 最大値を出力します
    print(max_sum)

if __name__ == '__main__':
    solve()

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