概要

連続する店舗の売上の合計が \(K\) 円以上になる区間の個数を求めます。

考察

この問題では、区間 \([l, r]\) の合計値が \(K\) 以上となるようなすべての \((l, r)\) の組の個数を答える必要があります。

素朴な方法として、すべての区間に対して合計を計算する方法がありますが、その計算量は \(O(N^3)\) や累積和を使っても \(O(N^2)\) となり、\(N\) が最大 \(2 \times 10^5\) なので現実的ではありません（TLE）。

そこで、「尺取り法（two pointers）」というテクニックを使います。

鍵となる観察

• 各右端 \(r\) を固定したとき、左端 \(l\) がある条件を満たせば、それより右にある \(l' > l\) も同様に条件を満たす可能性が高い。
• 特に、区間の和は単調性を持つので、左端を徐々に動かしながら条件を満たすかどうか判定できます。

さらに重要なポイント： - 区間 \([l, r]\) が条件を満たすとき、右端をそれ以上伸ばした区間（例：\([l, r+1], [l, r+2], \ldots, [l, N]\)）もすべて条件を満たす。 - つまり、右端が \(r\) 以上であるような条件を満たす区間の個数は \(N - r + 1\) 個あります。

この性質を利用することで、尺取り法により効率的に数えることができます。

アルゴリズム

1. まず、累積和を前計算しておきます。これにより任意の区間の和を \(O(1)\) で求められます。
   • prefix_sums[i] は \(V_1 + V_2 + \cdots + V_i\) （0-indexedで扱いやすくするために先頭に0を追加）
2. 右端 \(r\) を 1 から \(N\) まで動かします。
3. 各 \(r\) について、区間 \([l, r]\) の和が \(K\) 以上になる最小の \(l\) を求めます。
4. そのような \(l\) が見つかった場合、右端が \(r\) 以上で条件を満たす区間の個数（\(N - r + 1\)）を答えに加えます。
5. 左端 \(l\) を進めながら、次に右端を調べます。

このようにして、すべての条件を満たす区間の個数を高速に求めます。

計算量

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

実装のポイント

• 累積和の最初に 0 を入れておくことで、区間和の計算がシンプルになります。
• 尺取り法では、左端が進む回数は全体で最大でも \(N\) 回なので、全体で線形時間で処理可能です。
• count += N - right + 1 の部分が、現在の右端を含む条件を満たす区間の数を足している点が重要です。

## ソースコード

```python
import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    V = list(map(int, data[2:]))
    
    # 累積和を計算
    prefix_sums = [0] + list(accumulate(V))
    
    count = 0
    # 尺取り法 (two pointers)
    left = 0
    for right in range(1, N + 1):
        # 区間 [left, right) の和が K 以上になるまで left を進める
        while prefix_sums[right] - prefix_sums[left] >= K:
            count += N - right + 1
            left += 1
            
    print(count)

if __name__ == "__main__":
    main()

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