概要

長さ \(K\) の連続区間ごとの合計 \(S_i\) をすべて調べ、その最大値と最小値の差 \( \max(S_i) - \min(S_i)\) を求める問題です。

考察

連続する \(K\) 日間の合計は \(N-K+1\) 個あり、愚直に各 \(S_i\) を $\(S_i = A_i + A_{i+1} + \dots + A_{i+K-1}\)\( のように毎回 \)K\( 個足して求めると、計算量は \)O((N-K+1)K)\( になります。最悪の場合 \)N=K=10^5\( 近くになり、\)10^{10}$ 回程度の足し算が必要になってしまい、時間制限に間に合いません（TLE）。

ここで重要な気づきは、隣り合う区間の和は「差分」で更新できることです。
例えば - \(S_1 = A_1 + A_2 + \dots + A_K\) - \(S_2 = A_2 + A_3 + \dots + A_{K+1}\)

なので、\(S_2\) は \(S_1\) から \(A_1\) を引いて \(A_{K+1}\) を足したもの： $\(S_2 = S_1 - A_1 + A_{K+1}\)\( 同様に一般に \)\(S_{i+1} = S_i - A_i + A_{i+K}\)\( となります。これにより、各区間和を \)O(1)\( で更新でき、全体を \)O(N)$ で処理できます。更新しながら最小値・最大値を追跡すれば、最後に差を出すだけです。

（例）\(A=[1,3,2,5]\), \(K=2\)
- \(S_1=1+3=4\) - \(S_2=4-1+2=5\) - \(S_3=5-3+5=7\)
最大 \(7\)、最小 \(4\)、差は \(3\)。

アルゴリズム

1. 最初の区間和 \(S_1=\sum_{j=1}^{K} A_j\) を計算する。
2. \(mn=mx=S_1\) として、最小値・最大値を初期化する。
3. \(i=K, K+1, \dots, N-1\) について、現在の区間和を次で更新する： $\(window\_sum \leftarrow window\_sum + A_{i+1} - A_{i-K+1}\)$ （0-index の実装では window_sum += A[i] - A[i-K]）
4. 更新後の window_sum で \(mn, mx\) を更新する。
5. 最後に \(mx-mn\) を出力する。

これはいわゆる スライディングウィンドウ（尺取りの基本形） です。

計算量

• 時間計算量: \(O(N)\)（各要素を高々定数回扱う）
• 空間計算量: \(O(N)\)（配列 \(A\) を保持。入力を逐次処理すれば \(O(1)\) にもできる）

実装のポイント

• 最初の区間和を作った後、ループでは「入ってくる要素を足し、出ていく要素を引く」順で更新します。

• \(mn\) と \(mx\) は最初の区間和で初期化しないと、更新漏れで WA になりやすいです。

• 入力が大きいので、Python では sys.stdin.buffer.read() のような高速入力を使うと安定します。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    K = int(next(it))
    A = [int(next(it)) for _ in range(N)]

    window_sum = sum(A[:K])
    mn = mx = window_sum

    for i in range(K, N):
        window_sum += A[i] - A[i - K]
        if window_sum < mn:
            mn = window_sum
        if window_sum > mx:
            mx = window_sum

    print(mx - mn)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。