概要

この問題は、長さ \(N\) の数列の中から、連続する長さ \(K\) の区間の総和が \(0\) 以下である箇所の数を求める問題です。

考察

まず、素朴な方法（愚直な解法）を考えてみましょう。 各開始位置 \(i\)（\(1 \leq i \leq N-K+1\)）について、そこから始まる \(K\) 個の要素の和を計算し、それが \(0\) 以下かどうかを判定します。

しかし、この方法では \(1\) つの区間の和を求めるのに \(O(K)\) の時間がかかります。区間の数は約 \(N\) 個あるため、全体の計算量は \(O(N \times K)\) となります。 本問題の制約では \(N, K \leq 2 \times 10^5\) であるため、\(N \times K\) は最大で \(4 \times 10^{10}\) に達し、一般的な制限時間（2秒程度）以内には終わりません。

そこで、「隣り合う区間の和は、ほとんどの要素が共通している」という点に注目します。

例えば、\(N=5, K=3\) で数列 \(A = [A_1, A_2, A_3, A_4, A_5]\) の場合： 1. 最初の区間：\((A_1 + A_2 + A_3)\) 2. 次の区間：\((A_2 + A_3 + A_4)\)

この 2 つを比べると、共通部分 \((A_2 + A_3)\) を何度も計算し直すのは無駄であることがわかります。2 番目の和は、1 番目の和から \(A_1\) を引き、新たに \(A_4\) を加えるだけで計算できます。

アルゴリズム

この手法はスライディングウィンドウ法と呼ばれます。

1. まず、最初の区間（\(1\) 番目から \(K\) 番目まで）の合計 current_sum を計算します。
2. current_sum が \(0\) 以下なら、カウントを \(+1\) します。
3. 次に、ウィンドウを \(1\) つずつ右にずらしていきます。
   • ウィンドウから外れる要素（左端）を current_sum から引きます。
   • 新しくウィンドウに入る要素（右端）を current_sum に足します。
   • 更新された current_sum が \(0\) 以下なら、カウントを \(+1\) します。
4. これを最後まで繰り返します。

この方法なら、各ステップの計算は「引き算 \(1\) 回と足し算 \(1\) 回」だけで済むため、非常に高速です。

計算量

• 時間計算量: \(O(N)\)
  • データの読み込みに \(O(N)\)、スライディングウィンドウによる走査に \(O(N)\) かかるため、全体で \(O(N)\) となります。\(N=2 \times 10^5\) であっても十分に間に合います。
• 空間計算量: \(O(N)\)
  • 入力された数列を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• データの入力: \(N\) や \(A_i\) の値が大きいため、Python の input() を何度も呼び出すよりも、sys.stdin.read().split() などを使って一括で読み込む方が高速です。
• 合計値の更新: current_sum += a[i + k] - a[i] のように、新しく入る要素のインデックスと出ていく要素のインデックスを正確に指定する必要があります。
• カウントの初期化: 最初の \(K\) 個の和をループの前に判定しておくことを忘れないようにしましょう。

ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを取得し、空白で分割します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N（データ数）とK（連続時間数）を取得します
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 各時間の品質指標を整数のリストとして取得します
    # map関数を使用することで、大量のデータを効率的に変換します
    a = list(map(int, input_data[2:]))
    
    # 最初のK時間の合計（最初のウィンドウ）を計算します
    current_sum = sum(a[:k])
    
    # 異常期間の個数をカウントする変数
    count = 0
    
    # 最初のウィンドウが異常期間（合計が0以下）であるか判定します
    if current_sum <= 0:
        count += 1
        
    # スライディングウィンドウを用いて、2番目以降のウィンドウの合計を効率的に計算します
    # i はウィンドウから外れる要素のインデックス、i + k は新しく入る要素のインデックスです
    for i in range(n - k):
        # 前の合計から外れる要素を引き、新しい要素を加えることで次の合計を求めます
        current_sum += a[i + k] - a[i]
        
        # 合計が0以下であれば異常期間としてカウントします
        if current_sum <= 0:
            count += 1
            
    # 結果を出力します
    print(count)

if __name__ == '__main__':
    solve()

この解説は gemini-3-flash-preview によって生成されました。