概要

旅行全体の費用を \(S\) 円とすると、合計が \(S-K\) 円となる連続区間を取りやめればよいです。各日の費用が正であることを利用し、尺取り法でそのような区間を数えます。

考察

取りやめる区間の合計に注目する

旅行全体の費用を \(S=\sum_{i=1}^{N} A_i\) とします。

区間 \([l,r]\) を取りやめた後の費用が \(K\) 円になる条件は、

\(S-\sum_{i=l}^{r} A_i=K\)

です。これを変形すると、

\(\sum_{i=l}^{r} A_i=S-K\)

となります。つまり、合計が \(S-K\) となる連続区間の個数を求める問題に置き換えられます。

ただし、先に次のケースを処理します。

• \(S<K\) の場合：予定を取りやめても費用は増えないため、答えは \(0\)。
• \(S=K\) の場合：何も取りやめない方法だけが条件を満たすため、答えは \(1\)。すべての \(A_i\) が正なので、1 日でも取りやめると費用は \(K\) より小さくなります。

以降は \(S>K\) とし、目標の区間和を \(T=S-K>0\) とします。

すべての区間を調べると間に合わない

連続区間は \(\frac{N(N+1)}{2}\) 個あります。累積和を使って各区間の合計を \(O(1)\) で求めても、すべて調べるには \(O(N^2)\) 時間かかります。

\(N\) は最大 \(10^6\) なので、この方法では実行時間制限に間に合いません。

各要素が正であることを利用する

すべての \(A_i\) が正なので、区間和には次の性質があります。

• 右端を右に動かして要素を追加すると、区間和は必ず増える。
• 左端を右に動かして要素を取り除くと、区間和は必ず減る。

したがって、右端を順に動かし、区間和が \(T\) を超えたときだけ左端を進める「尺取り法」が使えます。

一度、区間和が大きすぎて候補から外した左端は、右端をさらに伸ばしても区間和が増えるだけなので、再び調べる必要はありません。

また、右端を固定すると、左端を進めるたびに区間和が必ず減るため、合計が \(T\) になる左端は高々 1 つです。

アルゴリズム

コードに合わせて、配列の添字を \(0\) 始まりとします。

1. 配列を読み込み、全体の合計 \(S\) を求めます。
2. \(S<K\) なら \(0\)、\(S=K\) なら \(1\) を出力して終了します。
3. \(T=S-K\) とし、左端 left、区間和 sum、答え answer をすべて \(0\) に初期化します。
4. 右端 right を \(0\) から \(N-1\) まで順に動かします。
   • sum に A[right] を加えます。
   • sum > T の間、sum から A[left] を引き、left を \(1\) 増やします。
   • sum == T なら、その区間を取りやめられるので、answer を \(1\) 増やします。
5. answer を出力します。

具体例

\(A=(1,2,1,3)\)、\(K=4\) とします。

全体の合計は \(S=7\) なので、合計が \(T=7-4=3\) となる区間を探します。

追加する要素	追加直後の区間和	左端を調整した後の区間	カウント
\(1\)	\(1\)	\((1)\)	しない
\(2\)	\(3\)	\((1,2)\)	する
\(1\)	\(4\)	\((2,1)\)	する
\(3\)	\(6\)	\((3)\)	する

条件を満たす取りやめ方は、1～2 日目、2～3 日目、4 日目の \(3\) 通りです。

正しく数えられる理由

各右端について、区間和が \(T\) を超えている間は、その区間を答えにできないため左端を進めます。取り除いた左端は、今後右端を伸ばしても区間和がさらに増えるので、将来の候補にもなりません。

調整後の区間和が \(T\) なら、その区間を数えます。\(T\) 未満なら、左端をさらに進めても区間和は減るだけなので、その右端で条件を満たす区間はありません。

これにより、条件を満たすすべての区間を重複なく数えられます。

計算量

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

while 文はありますが、左端は全体を通して最大 \(N\) 回しか進みません。右端も \(N\) 回動くだけなので、全体で \(O(N)\) 時間です。

配列 A の保存に \(O(N)\) の空間を使います。配列以外の追加領域は \(O(1)\) です。

実装のポイント

• 合計値には 64 ビット整数を使う
  全体の合計は最大 \(10^6\times 10^9=10^{15}\) です。total、K、target、sum には C++ の long long を使います。

• \(S=K\) は尺取り法の前に処理する
  「何も取りやめない」は 1 通りです。目標和を \(0\) として空区間を数えると、同じ方法を重複して数えるおそれがあります。

• 左端を進める条件は sum > target
  等しい場合は条件を満たす区間なので、縮めずに数えます。

• 空区間になる場合もある
  追加した要素だけで target を超える場合、調整後に left == right + 1、sum == 0 となります。ただし target > 0 なので、空区間が答えに数えられることはありません。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    long long K;
    cin >> N >> K;

    vector<int> A(N);
    long long total = 0;
    for (int &a : A) {
        cin >> a;
        total += a;
    }

    if (total < K) {
        cout << 0 << '\n';
        return 0;
    }
    if (total == K) {
        cout << 1 << '\n';
        return 0;
    }

    const long long target = total - K;
    long long sum = 0, answer = 0;
    int left = 0;

    for (int right = 0; right < N; ++right) {
        sum += A[right];
        while (sum > target) {
            sum -= A[left++];
        }
        if (sum == target) {
            ++answer;
        }
    }

    cout << answer << '\n';
    return 0;
}

---

この解説は gpt-6-astra-medium によって生成されました。