概要

この問題は、長さ \(N\) の数列の中から、合計が \(K\) 以上となる「連続する部分列」がいくつあるかを数える問題です。

考察

1. 素直な方法（全探索）

まず、すべての連続区間 \((l, r)\) を調べる方法を考えてみます。 \(1 \leq l \leq r \leq N\) となる組をすべて列挙すると、その個数はおよそ \(\frac{N^2}{2}\) 通りとなります。今回の制約では \(N = 2 \times 10^5\) であるため、区間の数は約 \(2 \times 10^{10}\) 個にもなり、一つずつ合計を計算していては実行時間制限に間に合いません（TLEとなります）。

2. 重要な性質：単調性

この問題の重要な点は、「すべての売上 \(V_i\) が正の整数である」ということです。 この性質により、ある区間 \([l, r]\) の合計が \(K\) 以上であるとき、その右端 \(r\) をさらに右に伸ばした区間（ \([l, r+1], [l, r+2], \dots, [l, N]\) ）の合計も、必ず \(K\) 以上になります。

つまり、各左端 \(l\) に対して、「合計が \(K\) 以上になる最小の右端 \(r\)」を見つけることができれば、それより右側にあるすべての \(r\)（合計 \(N - r + 1\) 個）が条件を満たすことがわかります。

3. 効率的な解法

「左端 \(l\) を右に一つ進めると、条件を満たす最小の右端 \(r\) も右（または同じ位置）に移動する」という性質を利用します。これを用いると、「しゃくとり法」と呼ばれる手法で効率的に解くことができます。

アルゴリズム

しゃくとり法

以下の手順でカウントを行います。

1. 左端のインデックス left を \(0\) から \(N-1\) まで動かします。
2. 各 left に対して、現在の区間合計 current_sum が \(K\) 未満である間、右端のインデックス right を進めながら V[right] を足していきます。
3. current_sum が \(K\) 以上になったら、その時点の right から最後までの店舗数 (N - right + 1) を答えに加算します。
   • ※コード上では、right を進めた後に right += 1 をしているため、加算する数は N - right + 1 となります。
4. 次の left に備えて、現在の V[left] を current_sum から引きます。

計算量

• 時間計算量: \(O(N)\)
  • left と right の 2 つのポインタは、それぞれ高々 \(N\) 回しか移動しません。全体で数列を 1〜2 周する程度の計算量で済むため、非常に高速です。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の売上データをリストに保持するためのメモリが必要です。

実装のポイント

• 合計値の型: \(K\) は最大 \(10^{14}\)、売上の合計はさらに大きくなる可能性があるため、プログラミング言語によっては 64bit 整数型（Pythonでは自動で扱われます）を使用する必要があります。

• 右端の管理: while ループの中で right が \(N\) を超えないように制御しつつ、条件を満たした瞬間に残りの個数をまとめて計算するのが効率的です。

• 累積和との比較: しゃくとり法の代わりに、累積和を計算したあとに二分探索（bisect）を用いて各 \(l\) に対する最小の \(r\) を探す方法でも \(O(N \log N)\) で解くことが可能です。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 店舗数, K: 目標売上
    N = int(input_data[0])
    K = int(input_data[1])
    # V: 各店舗の売上リスト
    V = list(map(int, input_data[2:]))
    
    ans = 0
    right = 0
    current_sum = 0
    
    # しゃくとり法を用いて条件を満たす区間の個数を数える
    for left in range(N):
        # 合計が K 以上になるまで右端を進める
        while right < N and current_sum < K:
            current_sum += V[right]
            right += 1
            
        # 合計が K 以上になった場合
        # 現在の left に対して、right-1 以降のすべての右端 index が条件を満たす
        if current_sum >= K:
            ans += (N - right + 1)
            
        # 左端を一つ進める準備として、現在の left の値を合計から引く
        current_sum -= V[left]
        
    # 結果を出力
    print(ans)

if __name__ == '__main__':
    solve()

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