概要

\(N\) 日間の気温データから、連続する \(K\) 日間の合計値をすべて計算し、その中の「最大値」と「最小値」の差を求める問題です。

考察

素朴な方法（愚直な計算）

各 \(i\) について、\(S_i = A_i + A_{i+1} + \dots + A_{i+K-1}\) をその都度 \(K\) 個の要素を足して計算するとどうなるでしょうか。 一つの合計値を出すのに \(O(K)\) の計算量がかかり、合計値は \(N-K+1\) 個あるため、全体の計算量は \(O(N \times K)\) となります。 制約を見ると \(N, K \leq 10^5\) であるため、最悪の場合 \(10^{10}\) 回程度の計算が必要になり、実行時間制限に間に合いません（TLEとなります）。

効率的な計算方法（スライディングウィンドウ）

連続する区間の合計を計算する際、隣り合う区間 \(S_i\) と \(S_{i+1}\) は、その大部分が重複していることに注目します。

• \(S_i = \color{red}{A_i} + \underbrace{A_{i+1} + \dots + A_{i+K-1}}_{共通部分}\)
• \(S_{i+1} = \underbrace{A_{i+1} + \dots + A_{i+K-1}}_{共通部分} + \color{blue}{A_{i+K}}\)

この関係から、次の合計値 \(S_{i+1}\) は、現在の合計値 \(S_i\) から「一番左の要素 \(A_i\) を引き」、「新しく入る右の要素 \(A_{i+K}\) を足す」だけで求められることがわかります。 $\(S_{i+1} = S_i - A_i + A_{i+K}\)\( これなら、1つの合計値を求めるのにわずか 2 回の計算（加減算）で済むため、全体で \)O(N)$ の計算量で解くことが可能です。

アルゴリズム

1. 最初の \(K\) 日間の合計値 \(S_1\) を計算し、これを暫定の max_sum と min_sum に設定します。
2. 窓（ウィンドウ）を 1 つずつ右にずらしながら、以下の操作を \(i = 1\) から \(N-K\) まで繰り返します。
   • 現在の合計値から \(A_i\) を引き、\(A_{i+K}\) を足して新しい合計値を更新する。
   • 更新された合計値で max_sum と min_sum を更新する。
3. 最後に max_sum - min_sum を出力します。

計算量

• 時間計算量: \(O(N)\)
  • 最初の合計計算に \(O(K)\)、その後のスライドに \(O(N-K)\) かかるため、全体で \(O(N)\) となります。\(N=10^5\) でも十分に高速です。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の気温データをリストに保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 初期値の設定: max_sum と min_sum の初期値は、最初に計算した \(S_1\) に設定することで、正しく比較を始めることができます。

• ループの範囲: \(i\) 番目（0-indexed）の要素を捨てる際、次に新しく入る要素は \(i+K\) 番目になります。インデックスが範囲外にならないよう、ループの終端に注意が必要です。

• 高速な入力: Pythonで \(10^5\) 規模の入力を扱う場合、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: 各日の気温
    a = list(map(int, input_data[2:]))

    # 最初の K 日間の合計値を計算する (S_1)
    current_sum = sum(a[:k])
    max_sum = current_sum
    min_sum = current_sum

    # スライディングウィンドウを用いて、連続する K 日間の合計値を順次計算する
    # S_{i+1} = S_i - A_i + A_{i+K}
    for i in range(n - k):
        current_sum = current_sum - a[i] + a[i + k]
        
        # 合計値の最大値と最小値を更新する
        if current_sum > max_sum:
            max_sum = current_sum
        if current_sum < min_sum:
            min_sum = current_sum

    # 最大値と最小値の差を出力する
    print(max_sum - min_sum)

if __name__ == '__main__':
    solve()

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