概要

この問題は、与えられた数列から連続する部分列の和が \(K\) 以上になるような区間 \((l, r)\) の個数を求める問題です。

考察

素朴なアプローチとして、全ての区間 \((l, r)\) を列挙し、各区間の和を計算して \(K\) 以上かどうかを判定する方法が考えられます。しかし、この方法の時間計算量は \(O(N^2)\) であり、\(N\) が最大 \(2 \times 10^5\) と大きいため、実行時間制限に間に合いません。

そこで、効率的な解法としてスライディングウィンドウ法（または尺取り法）を使用します。この手法では、右端 \(r\) を固定したときに、条件を満たす最小の左端 \(l\) を見つけ、その \(l\) から \(r\) までの区間がすべて条件を満たすことを利用します。

アルゴリズム

1. 左端 \(l\) と現在の区間和 \(total\) を \(0\) で初期化します。
2. 右端 \(r\) を \(0\) から \(N-1\) まで順に動かします。
3. 各 \(r\) について、\(total\) に \(V[r]\) を加算します。
4. \(total \geq K\) である間、以下を繰り返します：
   • 現在の区間 \([l, r]\) が条件を満たすので、\(l\) を固定したときの条件を満たす区間は \([l, r], [l, r+1], ..., [l, N-1]\) の \(N - r\) 個あります。
   • \(count\) に \(N - r\) を加算します。
   • \(total\) から \(V[l]\) を減算し、\(l\) を \(1\) 増やします（ウィンドウを左から縮めます）。
5. 最終的に \(count\) を出力します。

このアルゴリズムでは、各要素は高々 \(2\) 回（右端として追加され、左端として削除される）しか処理されないため、効率的に動作します。

計算量

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

実装のポイント

• スライディングウィンドウ法では、左端 \(l\) と右端 \(r\) の \(2\) つのポインタを使用します。

• 条件を満たす区間が見つかったら、その左端 \(l\) から最後までのすべての区間が条件を満たすことを利用して、一気にカウントします。

• \(while\) ループの条件に \(left \leq right\) を入れることで、インデックスが範囲外になることを防ぎます。

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    K = int(data[1])
    V = list(map(int, data[2:2+n]))
    
    total = 0
    left = 0
    count = 0
    
    for right in range(n):
        total += V[right]
        while total >= K and left <= right:
            count += n - right
            total -= V[left]
            left += 1
            
    print(count)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。