概要

旅行全体から「1日も取りやめない」または「連続する区間を取りやめる」ことで、残りの費用の合計をちょうど \(K\) 円にする方法が何通りあるかを求める問題です。

考察

1. 問題の言い換え

旅行全体の費用合計を \(S = \sum_{i=1}^N A_i\) とします。 費用の決め方は次の2つのパターンに分かれます。

1. 予定を1日も取りやめない場合 かかる費用は \(S\) 円です。したがって、\(S = K\) であれば条件を満たす方法として \(1\) 通りカウントできます。

2. 区間 \([l, r]\) を取りやめる場合 取りやめた後の費用は \(S - \sum_{i=l}^r A_i\) 円です。これが \(K\) 円になるということは、 $\( \sum_{i=l}^r A_i = S - K \)$ が成り立つことを意味します。

したがって、目標値 \(T = S - K\) と置くと、この問題は「連続部分列の和がちょうど \(T\) となる区間 \([l, r]\) の個数を数える問題」に帰着されます。 なお、\(A_i \ge 1\) かつ \(1 \le l \le r \le N\) であるため、取りやめる区間の和は必ず \(1\) 以上です。そのため、\(T \le 0\) のときは条件を満たす区間は存在しません。

2. 素朴なアプローチと課題

すべての区間 \((l, r)\) を全探索する方法を考えると、区間の選び方は \(\frac{N(N+1)}{2} \approx \frac{10^{12}}{2}\) 通り存在します。 \(N \le 10^6\) であるため、この方法では実行時間制限に到底間に合わず TLE（実行時間超過）となってしまいます。

3. 効率的な解法

ここで、すべての \(A_i\) が正の整数（\(A_i \ge 1\)）であるという制約に注目します。 区間に含まれる要素がすべて正であるため、次のような単調性が成り立ちます。 - 区間の右端を右に伸ばすと、区間の和は必ず増加する。 - 区間の左端を右に縮めると、区間の和は必ず減少する。

この性質を利用することで、尺取り法（Two Pointers） を用いて \(O(N)\) で和が \(T\) となる区間を効率的に数え上げることができます。

アルゴリズム

1. 全体の費用の合計 \(S = \sum_{i=1}^N A_i\) を計算し、答えの変数を ans = 0 とする。
2. \(S = K\) であれば、予定を取りやめない方法が条件を満たすため ans を \(1\) 増やす。
3. 目標値 \(T = S - K\) を計算する。
4. \(T > 0\) の場合、尺取り法で和が \(T\) となる区間を数える：
   • 左端のポインタ left = 0、現在の区間の和 current_sum = 0 とする。
   • 右端のポインタ right を \(0\) から \(N-1\) まで進めながら以下を行う：
     1. current_sum に \(A_{\text{right}}\) を加える。
     2. current_sum > T かつ left <= right の間、current_sum から \(A_{\text{left}}\) を引き、left を \(1\) 進める。
     3. 縮めた結果 current_sum == T となれば、条件を満たす区間が見つかったので ans を \(1\) 増やす。
5. 最終的な ans の値を出力する。

各要素が正であるため、各 right に対して和が \(T\) となる left は高々 \(1\) つしか存在せず、重複や数え漏れなくカウントできます。

計算量

• 時間計算量: \(O(N)\)
  • 全体の合計の計算に \(O(N)\) かかります。
  • 尺取り法では、right と left の各ポインタがそれぞれ配列の左から右へ高々 \(N\) 回しか進まないため、\(O(N)\) で完了します。
  • 全体として \(O(N)\) であり、制約 \(N = 10^6\) に対して十分高速に動作します。
• 空間計算量: \(O(N)\)
  • 配列 \(A\) を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• オーバーフローの防止:

  • \(N \le 10^6\) かつ \(A_i \le 10^9\) のため、合計値 \(S\) は最大で \(10^{15}\) に達します。
  • \(K\) も最大 \(10^{15}\) であるため、費用の合計や目標値、答えの変数は 32bit 整数型（int）ではなく、64bit 整数型（C++ の long long）を使用する必要があります。

• \(T \le 0\) の処理:

  • \(S < K\) のときは \(T < 0\) となり、区間の和が負になることはないため区間を取りやめる方法では作れません。

  • \(S = K\) のときは \(T = 0\) となりますが、取りやめる区間は最低でも \(1\) 日以上（和は \(1\) 以上）でなければならないため、尺取り法の対象外となります（\(T > 0\) の条件分岐により安全にスキップされます）。

    ソースコード

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long k;
    if (!(cin >> n >> k)) return 0;

    vector<long long> a(n);
    long long total_sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        total_sum += a[i];
    }

    long long ans = 0;
    if (total_sum == k) {
        ans++;
    }

    long long target = total_sum - k;
    if (target > 0) {
        long long current_sum = 0;
        int left = 0;
        for (int right = 0; right < n; ++right) {
            current_sum += a[right];
            while (current_sum > target && left <= right) {
                current_sum -= a[left];
                left++;
            }
            if (current_sum == target) {
                ans++;
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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