概要

数列の中から連続する部分列を選び、その合計が指定された値 \(K\) になる選び方が何通りあるかを求める問題。

考察

この問題では、連続する部分列のうち、合計が \(K\) となるものを数える必要があります。

素朴なアプローチ

まず考えられるのが、すべての区間 \([l, r]\) を全探索して、それぞれの区間の合計を計算する方法です。これは二重ループで実現可能ですが、時間計算量が \(O(N^2)\) となり、制約 \(N \leq 2 \times 10^5\) のもとでは現実的ではありません（TLEします）。

効率的なアプローチ

ここで重要なのは「累積和」の考え方です。

数列 \(A\) の累積和を \(S\) とすると、\(S_i = A_1 + A_2 + \cdots + A_i\) と定義されます（\(S_0 = 0\)）。
このとき、区間 \([l, r]\) の合計は \(S_r - S_{l-1}\) で求められます。

したがって、「区間の合計が \(K\) である」という条件は次のように言い換えられます： $\( S_r - S_{l-1} = K \quad \Leftrightarrow \quad S_{l-1} = S_r - K \)$

つまり、今見ている位置 \(r\) に対して、過去に出現した累積和の中で \(S_r - K\) に等しいものがいくつあったかを数えられれば良いのです。

これを効率的に実現するために、累積和の出現回数を記録する辞書（ハッシュテーブル）を使います。

• 各要素を左から見ていく
• その時点での累積和を更新
• その累積和から \(K\) を引いた値が過去に何回出現したかを調べる
• 最後に現在の累積和を記録

これにより、各要素に対して定数時間で処理できるので、全体で \(O(N)\) で解けます。

アルゴリズム

1. 累積和の出現回数を記録する defaultdict を用意し、初期値として \(0\) の出現回数を1にしておく（空の部分列に対応）
2. 左から順番に要素を見ていく
3. 現在の累積和 current_sum を更新
4. current_sum - K が過去に出現していた回数を答えに加算
5. 現在の累積和を記録（出現回数をインクリメント）
6. 最終的な答えを出力

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 累積和の初期値 \(S_0 = 0\) を忘れずに登録する（acc_count[0] = 1）
• 辞書を使うことで、特定の値の出現回数を高速に取得できる
• 各要素を一度だけ見るため、非常に効率的

## ソースコード

```python
from collections import defaultdict

N, K = map(int, input().split())
A = list(map(int, input().split()))

# 累積和とその出現回数を保持する辞書
acc_count = defaultdict(int)
acc_count[0] = 1  # 空の部分列の累積和は0

count = 0
current_sum = 0

for i in range(N):
    current_sum += A[i]
    # これまでの累積和で、(現在の累積和 - K) に等しいものが何個あるかを調べる
    count += acc_count[current_sum - K]
    # 現在の累積和を記録
    acc_count[current_sum] += 1

print(count)

---

この解説は qwen3-coder-480b によって生成されました。