概要

\(N\) 日間の気温データに対して、すべての連続 \(K\) 日間の合計値を求め、その最大値と最小値の差を計算する問題です。スライディングウィンドウ（尺取り法）を用いて効率的に解くことができます。

考察

素朴なアプローチとその問題点

最も単純な方法は、\(i = 1, 2, \dots, N-K+1\) のそれぞれについて \(S_i = A_i + A_{i+1} + \dots + A_{i+K-1}\) を毎回 \(K\) 個の要素を足して計算することです。この場合、各 \(S_i\) の計算に \(O(K)\) かかり、全体で \(O((N-K+1) \times K)\) となります。\(N\) が最大 \(10^5\) のとき、最悪 \(O(N^2)\) 程度になり、TLE（実行時間超過）の恐れがあります。

重要な気づき：隣り合う区間の差

連続する2つの区間に注目すると、大部分が重なっていることが分かります。

\[S_i = A_i + A_{i+1} + \dots + A_{i+K-1}\]

\[S_{i+1} = A_{i+1} + A_{i+2} + \dots + A_{i+K}\]

この2つの差を取ると、

\[S_{i+1} = S_i - A_i + A_{i+K}\]

つまり、\(S_i\) が分かっていれば、先頭の要素を引いて末尾に新しい要素を足す だけで \(S_{i+1}\) が \(O(1)\) で求まります。これがスライディングウィンドウの考え方です。

具体例

\(N = 6, K = 3\)、気温データが [2, 5, 3, 7, 1, 4] の場合：

最大値は \(15\)、最小値は \(10\) なので、答えは \(15 - 10 = 5\) です。

アルゴリズム

1. 初期化: 最初の \(K\) 個の要素の合計 \(S_1\) を計算し、暫定の最大値・最小値を \(S_1\) に設定する。
2. スライド: \(i = 2, 3, \dots, N-K+1\) について、以下を繰り返す。
   • \(S_i = S_{i-1} - A_{i-1} + A_{i+K-1}\) で合計値を更新する。
   • 最大値・最小値を更新する。
3. 出力: 最大値と最小値の差を出力する。

計算量

• 時間計算量: \(O(N)\)（初期の合計計算に \(O(K)\)、スライドに \(O(N-K)\) で、合わせて \(O(N)\)）
• 空間計算量: \(O(N)\)（配列 \(A\) の保持に必要。合計値は1変数で管理するため追加は \(O(1)\)）

実装のポイント

• \(S_i\) をすべて配列に保存する必要はありません。現在の合計値を1つの変数 S で管理し、スライドのたびに更新すれば十分です。これにより余分なメモリを使わずに済みます。

• 最大値・最小値も逐次更新することで、全体を通して1回のループで答えが求まります。

• ループのインデックスに注意してください。S += A[i + K - 1] - A[i - 1] で、追加する要素と除去する要素の添字を正しく設定することが重要です。

  ソースコード

N, K = map(int, input().split())
A = list(map(int, input().split()))

S = sum(A[:K])
ma = S
mi = S
for i in range(1, N - K + 1):
    S += A[i + K - 1] - A[i - 1]
    if S > ma:
        ma = S
    if S < mi:
        mi = S

print(ma - mi)

この解説は claude4.6opus-thinking によって生成されました。