概要

長さ \(N\) の正整数からなる数列から、要素の合計が \(K\) 以下となる連続部分列の個数を数える問題です。尺取り法（Two Pointers）を用いて効率的に解きます。

考察

素朴なアプローチとその問題点

すべての区間 \((l, r)\) を試す方法を考えると、区間の選び方が \(O(N^2)\) 通りあり、各区間の合計計算に \(O(N)\) かかると全体で \(O(N^3)\) となります。累積和を使っても \(O(N^2)\) で、\(N = 2 \times 10^5\) では TLE になります。

重要な気づき：単調性

この問題では すべての要素が正 という条件があります。これにより以下の性質が成り立ちます：

• 区間を広げると合計は必ず増える
• 区間を狭めると合計は必ず減る

この単調性を利用すると、尺取り法が適用できます。

尺取り法の着想

右端を \(r\) に固定したとき、「合計が \(K\) 以下となる最小の左端 \(l\)」を求められれば、左端が \(l, l+1, \ldots, r\) のどれでも条件を満たします（区間を狭めると合計が減るため）。

さらに、\(r\) を 1 増やすと合計が増えるので、新しい最小の左端は前の左端以上になります。つまり、左端は右にしか動かないので、全体で \(O(N)\) で処理できます。

アルゴリズム

1. 左端 left = 0、現在の区間の合計 current_sum = 0、答え count = 0 で初期化
2. 右端 right を \(0\) から \(N-1\) まで順に動かす：
   • current_sum に A[right] を加える
   • current_sum > K の間、A[left] を引いて left を右に進める
   • この時点で区間 \([left, right]\) の合計は \(K\) 以下
   • 右端が right で条件を満たす区間は right - left + 1 個
   • count にこの個数を加算
3. count を出力

具体例（\(N=5, K=10, A=[3, 1, 4, 1, 5]\)）

right	A[right]	current_sum	left	条件を満たす区間数
0	3	3	0	1（[3]）
1	1	4	0	2（[3,1], [1]）
2	4	8	0	3（[3,1,4], [1,4], [4]）
3	1	9	0	4
4	5	14→10	1	4（[1,4,1,5]など）

答え: \(1+2+3+4+4 = 14\)

計算量

• 時間計算量: \(O(N)\)
  • right は \(N\) 回進み、left も合計で高々 \(N\) 回しか進まないため
• 空間計算量: \(O(N)\)
  • 配列 \(A\) の格納に必要

実装のポイント

• left <= right の条件を while ループに入れることで、すべての要素が \(K\) より大きい場合も正しく処理できる

• current_sum と K は最大 \(10^{14}\) 程度になるため、64ビット整数が必要（Pythonでは自動で対応）

• 要素がすべて正なので、current_sum <= K を満たせば left から right までのすべての区間が条件を満たす

  ソースコード

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    count = 0
    current_sum = 0
    left = 0
    
    for right in range(N):
        current_sum += A[right]
        
        # 合計がKを超える間、左端を右に移動
        while current_sum > K and left <= right:
            current_sum -= A[left]
            left += 1
        
        # left から right までの区間で、合計がK以下
        # この時、右端がrightで左端がleft, left+1, ..., right となる区間はすべてK以下
        # （すべての要素が正なので、区間を狭めれば合計は減る）
        if current_sum <= K:
            count += (right - left + 1)
    
    print(count)

solve()

---

この解説は claude4.5opus によって生成されました。