概要

正の整数列 \(A\) に対して、「長さが \(K\) 以上」かつ「区間和が \(M\) 以上」となる連続区間 \((l,r)\) の個数を、尺取り法（2 ポインタ）で高速に数えます。

考察

重要な気づき

• \(A_i \ge 1\) なので、右端 \(r\) を右に伸ばすと区間和は 必ず増加 します。
• ある左端 \(l\) を固定したとき、条件（長さ \(\ge K\) かつ 和 \(\ge M\)）を初めて満たす最小の右端を \(r^\*\) とすると、
  • \(r \ge r^\*\) のすべての区間 \([l,r]\) も条件を満たします（右に伸ばせば和が減らないため）。
  • よって、左端 \(l\) に対する答えへの寄与は \(N - r^\* + 1\) 個 になります。

素朴解がなぜ無理か

全ての \((l,r)\) を試して区間和を計算すると、区間は \(O(N^2)\) 個あります。
\(N \le 2\times 10^5\) なので \(O(N^2)\) は到底間に合いません。

どう解決するか

「左端 \(l\) を 1 ずつ進めながら、右端 \(r\) は必要な分だけ右に進める」尺取り法を使います。 - \(r\) は決して左に戻さない（単調増加） - よって、\(r\) の移動回数は全体で高々 \(N\) 回になり、全体 \(O(N)\) で数えられます。

アルゴリズム

区間を 半開区間 \([l, r)\)（\(l\) を含み、\(r\) は含まない）で管理します。区間和を \(s\) とします。

1. 初期化：\(l=0, r=0, s=0, ans=0\)
2. 左端 \(l\) を \(0\) から \(N-1\) まで動かす：
   1. まず「長さが \(K\) 以上」を満たすまで右端を伸ばす
      
      • while \(r < N\) かつ \(r-l < K\)：\(s += A[r]\), \(r += 1\)
      • これでも長さが足りない（\(r-l < K\)）なら、以降どの \(l\) でも不可能なので終了
   2. 次に「和が \(M\) 以上」を満たすまで右端を伸ばす
      
      • while \(r < N\) かつ \(s < M\)：\(s += A[r]\), \(r += 1\)
   3. もし \(s \ge M\) なら、条件を満たす最小の右端は現在の \(r\)（ただし \([l, r)\) なので実際の右端は \(r-1\)）
      
      • このとき、右端をこれ以上伸ばした区間もすべて条件を満たすため、個数は \(N - (r-1)\) 個
      • よって ans += N - r + 1
   4. もし \(s < M\) のまま \(r == N\) に到達したら、これ以上右に伸ばせないので終了（以降の \(l\) でも和はさらに小さくなる方向なので不可能）
   5. 次の \(l\) へ進む準備として、左端の要素 \(A[l]\) を区間から外す：\(s -= A[l]\)

具体例（イメージ）

例えば \(N=5, K=2\) のとき、ある \(l\) で最小の達成右端が \(r^\*=4\)（1-indexedで \(r^\*=4\)）なら、 - \((l,4), (l,5)\) の 2 個が達成 - これは \(N - r^\* + 1 = 5 - 4 + 1 = 2\) で一括計算できます。

計算量

• 時間計算量: \(O(N)\)
  （右端 \(r\) は全体で高々 \(N\) 回しか増えないため）
• 空間計算量: \(O(1)\)
  （入力配列以外は定数個の変数のみ）

実装のポイント

• 区間を \([l,r)\)（半開区間）で持つと、長さが \(r-l\) で扱いやすいです。

• ans += N - r + 1 の意味に注意：
  現在の区間は \([l,r)\) で、条件を満たす最小の「最後の要素の位置」は \(r-1\)。
  そこから \(N-1\) まで選べるので個数は \(N-(r-1)=N-r+1\) になります。

• \(s < M\) のまま \(r==N\) に達したら、それ以降の \(l\) でも達成不能なので break してよいです（\(A_i>0\) の単調性が根拠）。

  ソースコード

import sys

def main():
    it = list(map(int, sys.stdin.buffer.read().split()))
    N, K, M = it[0], it[1], it[2]
    A = it[3:]

    ans = 0
    r = 0
    s = 0

    for l in range(N):
        if r < l:
            r = l
            s = 0

        while r < N and r - l < K:
            s += A[r]
            r += 1
        if r - l < K:
            break

        while r < N and s < M:
            s += A[r]
            r += 1

        if s >= M:
            ans += N - r + 1
        else:
            break

        s -= A[l]

    print(ans)

if __name__ == "__main__":
    main()

---

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