概要

連続する \(K\) 個の要素の和が \(0\) 以下になる区間の個数を求めます。

考察

この問題では、すべての区間について和を計算してチェックするという素朴な方法が考えられます。しかし、そのような全探索は、区間の数が最大で \(N - K + 1\) 個あり、各区間の和の計算に \(O(K)\) かかるため、全体で \(O(NK)\) の計算量となり、制約が \(N, K \sim 2 \times 10^5\) であるため現実的ではありません（TLEになります）。

そこで、効率的に連続部分列の和を計算するために「累積和」または「スライディングウィンドウ（しゃりんそう）」のテクニックを使います。

具体的には、最初の区間の和を計算した後、次の区間に移るときに1つ前の要素を引いて、新しい要素を足すことで和を更新していきます。これにより、各区間の和が \(O(1)\) で求められ、全体の計算量が \(O(N)\) になります。

例えば、入力が A = [1, -3, 2, -1, 0]、\(K = 3\) のとき、

• 最初の区間：\(1 + (-3) + 2 = 0\) → 異常期間
• 次の区間：\((-3) + 2 + (-1) = -2\) → 異常期間
• 最後の区間：\(2 + (-1) + 0 = 1\) → 正常

このようにして、和を効率的に更新しながら条件を満たす区間の数を数えていきます。

アルゴリズム

1. 最初の \(K\) 要素の和を計算し、それが \(0\) 以下ならカウントアップする。
2. その後、区間を1つずつスライドさせながら、和を更新する：
   • 新しく加わる要素：\(A[i]\)
   • 取り除く要素：\(A[i - K]\)
3. 各ステップで和が \(0\) 以下かどうかを判定し、条件を満たせばカウントを増やす。
4. 最終的なカウントを出力する。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(1)\) （入力配列を除く）

実装のポイント

• 最初の区間の和を sum(A[:K]) で一度だけ計算するのがポイントです。
• ループ内での和の更新は current_sum += A[i] - A[i - K] で行います。
• 区間の開始位置は \(i = K\) から始まり、\(i < N\) の間ループさせます。

ソースコード

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

count = 0
current_sum = sum(A[:K])
if current_sum <= 0:
    count += 1

for i in range(K, N):
    current_sum += A[i] - A[i - K]
    if current_sum <= 0:
        count += 1

print(count)

この解説は qwen3-coder-480b によって生成されました。