概要

\(N\) 本の木が並んでおり、それぞれの木から収穫できる果物の数が与えられます。この中から「連続する \(K\) 本の木」を選んだとき、収穫できる果物の合計値の最小値を求める問題です。

考察

素朴なアプローチ

最も単純な方法は、すべての開始位置について \(K\) 本分の合計を計算することです。 - 1番目から \(K\) 本目の合計を計算する - 2番目から \(K+1\) 本目の合計を計算する - … - \(N-K+1\) 番目から \(N\) 本目の合計を計算する

しかし、この方法では1つの合計を求めるのに \(O(K)\) の時間がかかり、それを約 \(N\) 回繰り返すため、全体の計算量は \(O(N \times K)\) となります。 本問題の制約では \(N, K \leq 2 \times 10^5\) であるため、最大で \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限（通常2秒程度）に間に合いません。

効率的なアプローチ（スライディングウィンドウ）

隣り合う範囲の合計を比較すると、大部分の要素が重複していることに注目します。 例えば、\(K=3\) で「1〜3番目」から「2〜4番目」に移動する場合： - 1〜3番目の合計：\(A_1 + A_2 + A_3\) - 2〜4番目の合計：\(A_2 + A_3 + A_4\)

この2つの差は、「新しく入ってくる \(A_4\)」と「出ていく \(A_1\)」だけです。 つまり、前の範囲の合計がわかっていれば、次の範囲の合計は「新しい値を足して、古い値を引く」というわずか2つの操作（\(O(1)\)）で求めることができます。

アルゴリズム

スライディングウィンドウ法

1. 最初に、左端から \(K\) 本の木の合計 current_sum を計算します。これを暫定の最小値 min_sum とします。
2. ウィンドウを1つずつ右にずらしていきます。具体的には \(i = 0\) から \(N-K-1\) まで以下を繰り返します。
   • current_sum から \(A_i\) を引き、\(A_{i+K}\) を足します。
   • 更新された current_sum と min_sum を比較し、小さい方を新しい min_sum とします。
3. 最終的な min_sum が答えとなります。

計算量

• 時間計算量: \(O(N)\)
  • 最初の \(K\) 個の合計に \(O(K)\)、その後のスライド操作に \(O(N-K)\) かかるため、全体で \(O(N)\) となります。\(N=2 \times 10^5\) であっても十分に高速に動作します。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の要素をリストに保持するためのメモリが必要です。

実装のポイント

• 合計値の初期化: 最初の \(K\) 個の合計を出す際、Pythonでは sum(a[:k]) を使うと簡潔に書けます。

• ループの範囲: インデックスが範囲外（IndexError）にならないよう、ループの終端条件に注意が必要です。i 番目の要素を捨てて i+k 番目の要素を加える場合、i+k が n-1 まで到達するようにループを回します。

• 大きな値の扱い: 果物の総数は最大で \(2 \times 10^5 \times 10^9 = 2 \times 10^{14}\) に達しますが、Pythonは標準で多倍長整数をサポートしているため、オーバーフローを気にせず計算できます。

  ソースコード

import sys

def solve():
    # 入力を受け取る
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    a = list(map(int, input_data[2:]))
    
    # 最初のK本の合計を計算
    current_sum = sum(a[:k])
    min_sum = current_sum
    
    # スライディングウィンドウを用いて連続するK本の合計の最小値を求める
    for i in range(n - k):
        # ウィンドウを1つ右にずらす（左端を除き、右端を加える）
        current_sum = current_sum - a[i] + a[i + k]
        if current_sum < min_sum:
            min_sum = current_sum
            
    # 結果を出力
    print(min_sum)

if __name__ == "__main__":
    solve()

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