概要

長さ \(N\) の正整数列から、要素の合計が \(K\) 以下となる連続する部分列（区間）の個数を求める問題です。

考察

1. 素朴なアプローチ

すべての区間の組み合わせ \((l, r)\) を調べると、区間の個数は \(N(N+1)/2\) 個あります。\(N = 2 \times 10^5\) であるため、組み合わせの数は約 \(2 \times 10^{10}\) となり、全探索では制限時間内に計算が終わりません（\(O(N^2)\) の計算量）。より効率的な手法が必要です。

2. 単調性の利用

この問題の重要なポイントは、数列の各要素 \(A_i\) がすべて正の整数であるという点です。これにより、以下の性質（単調性）が成り立ちます。 - ある区間の右端を固定して左端を右へ動かす（区間を短くする）と、合計値は必ず減少する。 - ある区間の左端を固定して右端を右へ動かす（区間を長くする）と、合計値は必ず増加する。

この性質を利用すると、すべての区間を独立に調べるのではなく、左端と右端を効率よく動かしながら条件を満たす範囲を特定する「しゃくとり法（Two Pointers）」が適用できます。

アルゴリズム

しゃくとり法による数え上げ

「右端 \(right\) を \(1\) つずつ進めながら、合計が \(K\) を超えない範囲で左端 \(left\) をどこまで右に詰められるか」を管理します。

1. 現在の区間の合計 current_sum を保持する変数を用意します。
2. 右端 \(right\) を \(0\) から \(N-1\) まで順に動かします。
   • current_sum に \(A_{right}\) を加えます。
   • current_sum が \(K\) を超えている間、左端 \(left\) を右に動かし、current_sum から \(A_{left}\) を引きます。
3. このとき、右端を \(right\) としたときに条件を満たす左端の最小値が \(left\) であるなら、\(right\) を右端とする条件を満たす区間は以下の \((right - left + 1)\) 個存在することになります。
   • \([left, right], [left+1, right], \ldots, [right, right]\)
4. この個数を各 \(right\) について合計していくことで、答えが求まります。

具体例 (\(N=4, K=10, A=\{3, 5, 4, 7\}\))

• \(right=0\): current_sum=3 (\(\leq 10\))。個数: \(0-0+1 = 1\) ({3})
• \(right=1\): current_sum=8 (\(\leq 10\))。個数: \(1-0+1 = 2\) ({3,5}, {5})
• \(right=2\): current_sum=12 (\(> 10\))。\(left\) を進める。
  • current_sum から \(A_0=3\) を引く \(\rightarrow\) 9 (\(\leq 10\))。
  • 個数: \(2-1+1 = 2\) ({5,4}, {4})
• \(right=3\): current_sum=16 (\(> 10\))。\(left\) を進める。
  • \(A_1=5\) を引く \(\rightarrow\) 11 (\(> 10\))
  • \(A_2=4\) を引く \(\rightarrow\) 7 (\(\leq 10\))
  • 個数: \(3-3+1 = 1\) ({7})
• 合計: \(1+2+2+1 = 6\) 個

計算量

• 時間計算量: \(O(N)\)
  • 右端 \(right\) は \(N\) 回動きます。
  • 左端 \(left\) も合計で最大 \(N\) 回しか動きません。
  • よって、全体で数列を 2 回走査する程度の時間で処理が完了します。
• 空間計算量: \(O(N)\)
  • 数列 \(A\) を保持するためのメモリが必要です。

実装のポイント

• 総和の型: 合計値 \(K\) や答えの個数は非常に大きな値になる可能性があるため、プログラミング言語によっては 64bit 整数型（Python の場合は標準で対応）を使用する必要があります。

• 高速な入出力: \(N\) が大きいため、Python の場合は sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

  ソースコード

import sys

def solve():
    # 入力の読み込み
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    a = list(map(int, input_data[2:]))
    
    ans = 0
    left = 0
    current_sum = 0
    
    # しゃくとり法（スライディングウィンドウ）を用いて条件を満たす区間を数え上げる
    for right in range(n):
        current_sum += a[right]
        
        # 合計が K を超える間、左端を右に動かす
        while current_sum > k and left <= right:
            current_sum -= a[left]
            left += 1
        
        # 現在の right を右端とする条件を満たす区間の数は (right - left + 1) 個
        ans += (right - left + 1)
        
    print(ans)

if __name__ == "__main__":
    solve()

---

この解説は gemini-3-flash-preview によって生成されました。