概要

正の整数列 \(A\) に対して、和が \(K\) 以下になる連続部分区間（長さ \(1\) 以上）の個数を数えます。
\(N\) が最大 \(2 \times 10^5\) なので、全区間を調べるのではなく高速に数える必要があります。

考察

重要な気づき

• \(A_i \ge 1\)（すべて正）なので、区間を右に伸ばすほど区間和は 必ず増加 します。
• この性質により、「ある左端 \(l\) に対して、条件 \((\)区間和 \(\le K)\) を満たす最大の右端 \(r\)」は 単調に動く（\(l\) を 1 増やすと、最適な \(r\) は左に戻らない）ことが分かります。

素朴な方法がダメな理由

• 全ての区間 \((l, r)\) を列挙して和を計算すると、区間数は \(O(N^2)\)（最大で約 \(2 \times 10^{10}\)）になり、時間制限に間に合いません。
• 累積和を使って各区間和を \(O(1)\) で求めても、列挙自体が \(O(N^2)\) なので TLE になります。

どう解決するか

「二重ループに見えるが、右端ポインタを戻さない」しゃくとり法（two pointers） を使うと、全体で \(O(N)\) で数えられます。

アルゴリズム

2 つのポインタ \(l, r\) と、現在の区間 \([l, r)\)（右端は含まない）の和 \(s\) を管理します。

1. 初期状態：\(r = 0, s = 0, ans = 0\)
2. 各 \(l = 0, 1, \dots, N-1\) について次を行う：
   • 可能な限り右端 \(r\) を伸ばす
     条件 \(r < N\) かつ \(s + A[r] \le K\) の間、
     \(s \leftarrow s + A[r]\), \(r \leftarrow r + 1\)
   • このとき、左端が \(l\) の条件を満たす区間は [ [l,l], [l,l+1], \dots, [l,r-1] ] の合計 \(r-l\) 個あるので、\(ans \leftarrow ans + (r-l)\)
   • 次の \(l\) に進めるために、区間から \(A[l]\) を外す：
     • ただし \(r==l\)（区間が空で、しかも \(A[l]\) を入れると \(K\) を超える等）だと進まなくなるので、 その場合は \(r \leftarrow r+1\) として強制的に進める
     • そうでなければ \(s \leftarrow s - A[l]\)

具体例

例：\(A = [2,1,3],\ K=3\) - \(l=0\)：\([2]\)（OK）, \([2,1]\)（OK）, \([2,1,3]\)（NG）→ \(r=2\) なので \(2\) 個加算 - \(l=1\)：今の \(r=2\) から伸ばすと \(1+3=4\) で NG → \([1]\) のみで \(1\) 個 - \(l=2\)：\([3]\)（OK）→ \(1\) 個
合計 \(2+1+1=4\)

計算量

• 時間計算量: \(O(N)\)
  （\(r\) は全体で最大 \(N\) 回しか増えないため、while を含めても線形）
• 空間計算量: \(O(1)\)
  （入力配列以外は定数個の変数のみ）

実装のポイント

• \(A_i\) が正だからこそ、しゃくとり法の「右端が戻らない」単調性が成立します（負数があると崩れます）。

• ans += r - l の意味は「左端 \(l\) 固定で作れる有効区間の個数」。

• if r == l: r += 1 は、条件を満たす区間が 1 つも作れないときに無限ループを防ぐための重要な処理です。

• \(K\) は最大 \(10^{14}\) なので、区間和 \(s\) は 64bit 整数相当が必要（Python は問題なし）。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    r = 0
    s = 0
    ans = 0

    for l in range(N):
        while r < N and s + A[r] <= K:
            s += A[r]
            r += 1
        ans += r - l
        if r == l:
            r += 1
        else:
            s -= A[l]

    print(ans)

if __name__ == "__main__":
    main()

---

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