概要

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

考察

素朴なアプローチとして、すべての連続 \(K\) 日間の合計値を個別に計算すると、合計値の数が \(N-K+1\) 個あり、それぞれの計算に \(O(K)\) の時間がかかるため、全体で \(O(NK)\) の時間計算量となります。\(N\) と \(K\) が最大 \(10^5\) であるため、最悪ケースでは \(10^{10}\) 回の計算が必要となり、実行時間制限に間に合いません。

しかし、連続する \(K\) 日間の合計値は、隣接する区間の合計値と大部分が重複していることに注目します。具体的には、\(S_i\) と \(S_{i+1}\) の差は、\(A_i\) が抜けて \(A_{i+K}\) が加わるだけです。この性質を利用すれば、次の区間の合計値を定数時間で計算できます。

アルゴリズム

1. 最初の \(K\) 日間の合計値を計算します。
2. この合計値を最大値と最小値の初期値とします。
3. 区間を1日ずつスライドさせながら、合計値を更新します：
   • 現在の区間の合計値から、区間の最初の日の気温を引きます。
   • 次の日の気温を加えます。
4. 更新した合計値を使って、最大値と最小値を更新します。
5. すべての区間を処理した後、最大値と最小値の差を出力します。

この手法は「スライディングウィンドウ」と呼ばれ、連続する部分区間の合計を効率的に計算できます。

計算量

• 時間計算量: \(O(N)\)
  • 最初の合計値の計算に \(O(K)\)、その後のループで \(O(N-K)\) の計算を行うため、全体で \(O(N)\) です。
• 空間計算量: \(O(N)\)
  • 気温データを格納するための配列が必要です。

実装のポイント

• 最初の区間の合計値を計算した後、ループでは減算と加算のみで合計値を更新します。

• 最大値と最小値は毎回比較して更新します。

• 入力の読み込みでは、一度にすべてのデータを読み込むことで効率化しています。

  ソースコード

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    k = int(data[1])
    A = list(map(int, data[2:2+n]))
    
    total = sum(A[:k])
    max_sum = total
    min_sum = total
    
    for i in range(1, n - k + 1):
        total = total - A[i-1] + A[i+k-1]
        if total > max_sum:
            max_sum = total
        if total < min_sum:
            min_sum = total
            
    print(max_sum - min_sum)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。