概要

長さ \(K\) の連続区間（スライドする窓）それぞれについて、要素和が \(0\) 以下になる区間の個数を数える問題です。

考察

各開始位置 \(i\)（\(1 \le i \le N-K+1\)）について区間 \(A_i, A_{i+1}, \ldots, A_{i+K-1}\) の合計を調べれば答えは出ます。

しかし素朴に「各区間の和を毎回 \(K\) 個足して求める」と、区間は \(N-K+1\) 個あり、各回に \(K\) 回の加算が必要なので合計で \(O(NK)\) になります。
制約は最大 \(N=2\times10^5\) なので、例えば \(K\) も同程度だと \(O(NK)\) は現実的な時間では終わりません（TLEの原因）。

ここで重要な気づきは、隣り合う長さ \(K\) の区間同士は ほとんど同じ要素を共有している ことです。
例えば

• 1つ目の区間: \(A_1 + A_2 + \cdots + A_K\)
• 2つ目の区間: \(A_2 + A_3 + \cdots + A_{K+1}\)

この2つの差は「\(A_1\) が抜けて \(A_{K+1}\) が入る」だけなので、

\[ \text{sum}_{2} = \text{sum}_{1} - A_1 + A_{K+1} \]

と、定数時間で更新できます。これにより全体を \(O(N)\) にできます。

アルゴリズム

スライディングウィンドウ（尺取りの窓更新）で解きます。

1. まず最初の区間 \(A_1 \sim A_K\) の合計 \(s\) を計算する。
2. \(s \le 0\) なら答えに 1 加算する。
3. 区間の右端を1つずつ進める（\(i=K\) から \(N-1\) まで）とき、次の式で和を更新する：
   • 新しく入る要素: \(A_i\)
   • 抜ける要素: \(A_{i-K}\)
   • 更新: \(s \leftarrow s + A_i - A_{i-K}\)
4. 更新後の \(s \le 0\) を満たすたびに答えを加算する。
5. 最終的なカウントを出力する。

（例）\(A=[2, -5, 1, 1], K=2\)
最初: \(2+(-5)=-3 \le 0\) → 1個
次: \(-3 + 1 - 2 = -4 \le 0\) → 2個
次: \(-4 + 1 - (-5) = 2\) → 増えない
答えは 2 個。

計算量

• 時間計算量: \(O(N)\)（各要素を高々1回ずつ「入る」「出る」で処理）
• 空間計算量: \(O(1)\)（合計値とカウンタ程度。入力配列を除く追加領域）

実装のポイント

• 最初の区間和 sum(A[:K]) を作ってから、以降は s += A[i] - A[i-K] で更新するとシンプルです。
• 判定は「\(0\) 以下」なので条件は s <= 0 です（< 0 と間違えない）。
• \(N\) が大きいので、入力は sys.stdin.readline を使うと安定します。

ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    s = sum(A[:K])
    ans = 1 if s <= 0 else 0
    
    for i in range(K, N):
        s += A[i] - A[i - K]
        if s <= 0:
            ans += 1
    
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。