概要

連続する \(K\) 個の要素の合計が \(0\) 以下となる区間の個数を数える問題です。スライディングウィンドウを使うことで効率的に解くことができます。

考察

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

最も単純な方法は、各開始位置 \(i\) に対して毎回 \(K\) 個の要素の合計を計算することです。

for i in range(N - K + 1):
    window_sum = sum(A[i:i+K])  # 毎回K個の要素を足す
    if window_sum <= 0:
        count += 1

この方法では、区間の数が \(O(N)\) 個あり、各区間で \(O(K)\) 回の足し算を行うため、全体で \(O(NK)\) の計算量がかかります。\(N = 2 \times 10^5\) の場合、最悪で \(4 \times 10^{10}\) 回程度の計算が必要となり、TLE（時間超過）になってしまいます。

重要な気づき

連続する2つの区間を考えてみましょう。

• 区間1: \(A_1, A_2, A_3, A_4\) （\(K=4\) の場合）
• 区間2: \(A_2, A_3, A_4, A_5\)

この2つの区間は \(A_2, A_3, A_4\) の部分が重複しています。つまり、区間1の合計から区間2の合計を求めるには：

\[\text{区間2の合計} = \text{区間1の合計} - A_1 + A_5\]

と、たった2回の演算で計算できます。

アルゴリズム

スライディングウィンドウ（尺取り法） を使います。

1. まず最初の \(K\) 個の要素の合計を計算する
2. ウィンドウを1つずつ右にスライドさせながら：
   • 左端の要素を引く
   • 右端に新しい要素を足す
3. 各ステップで合計が \(0\) 以下かどうかを判定し、カウントする

具体例（\(N=6, K=3, A=[2, -3, 1, -2, 4, -1]\)）：

位置 \(i\)	区間	計算方法	合計	異常？
1	\([2, -3, 1]\)	初期計算	\(0\)	✓
2	\([-3, 1, -2]\)	\(0 - 2 + (-2) = -4\)	\(-4\)	✓
3	\([1, -2, 4]\)	\(-4 - (-3) + 4 = 3\)	\(3\)	×
4	\([-2, 4, -1]\)	\(3 - 1 + (-1) = 1\)	\(1\)	×

答え：\(2\) 箇所

計算量

• 時間計算量: \(O(N)\)

  • 最初の \(K\) 個の合計計算: \(O(K)\)
  • スライディングウィンドウの移動: \(O(N - K)\) 回、各回 \(O(1)\)
  • 合計: \(O(K + (N - K)) = O(N)\)

• 空間計算量: \(O(N)\)

  • 入力配列 \(A\) の格納に \(O(N)\)
  • その他の変数は \(O(1)\)

実装のポイント

1. オーバーフローに注意: \(A_i\) の絶対値が最大 \(10^9\)、\(K\) が最大 \(2 \times 10^5\) なので、合計値は最大 \(2 \times 10^{14}\) 程度になります。Pythonでは整数のオーバーフローを気にする必要はありませんが、C++などでは long long を使う必要があります。

2. インデックスの管理: ウィンドウを右にスライドする際、削除する要素は A[i-1]、追加する要素は A[i+K-1] となります。インデックスのずれに注意しましょう。

3. 境界条件: \(K = N\) の場合、区間は1つだけです。コードがこのケースを正しく処理できるか確認しましょう（ループが0回実行されるので問題ありません）。

ソースコード

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # 最初のK個の合計を計算
    window_sum = sum(A[:K])
    
    count = 0
    if window_sum <= 0:
        count += 1
    
    # スライディングウィンドウで残りの区間をチェック
    for i in range(1, N - K + 1):
        # 新しい要素を追加し、古い要素を削除
        window_sum = window_sum - A[i - 1] + A[i + K - 1]
        if window_sum <= 0:
            count += 1
    
    print(count)

solve()

---

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