概要

この問題は、長さ \(N\) の数列 \(A\) から、長さが \(K\) 以上であり、かつその区間の総和に \(C\) を掛けた値が \(T\) 以下となるような連続する部分区間 \((l, r)\) の個数を求める問題です。

考察

1. 式の単純化

問題の条件式は \(C \times (A_l + A_{l+1} + \cdots + A_r) \leq T\) です。 これを変形すると、 $\(A_l + A_{l+1} + \cdots + A_r \leq \lfloor \frac{T}{C} \rfloor\)\( となります（ \)A_i\( は整数なので、右辺は切り捨て除算で問題ありません）。 あらかじめ \)M = \lfloor \frac{T}{C} \rfloor\( と置いておくことで、条件は「区間の和が \)M$ 以下」というシンプルな形に整理できます。

2. ナイーブな解法の限界

すべての \((l, r)\) の組を愚直に調べると、組の数が \(O(N^2)\) 個存在するため、全体の計算量は \(O(N^2)\) となります。 本問題の制約は \(N \leq 2 \times 10^6\) であるため、 \(O(N^2)\) の解法では実行時間制限に間に合わず、TLE（実行時間制限超過）になってしまいます。 したがって、より高速な \(O(N)\) のアプローチを考える必要があります。

3. 単調性の利用と「尺取り法」

配列 \(A\) の要素はすべて \(1\) 以上の整数です。そのため、左端 \(l\) を固定したとき、右端 \(r\) を右に進める（増やす）ほど、区間の和は単調に増加します。 この単調性を利用すると、以下のような性質が成り立ちます。

• 左端 \(l\) に対して、条件（区間和 \(\leq M\)）を満たす最大の右端を \(max\_r\) とします。
• 次に左端を \(l+1\) に進めたとき、条件を満たす最大の右端は、必ず \(max\_r\) 以上になります（左端を右に動かすと、区間和が減少するか等しいため、右端をさらに右に伸ばせる可能性があるからです）。

この性質を利用して、右端を指すポインタを巻き戻すことなく右に進めていく尺取り法（Two Pointers）を適用することができます。

アルゴリズム

区間和を高速に計算するために、あらかじめ累積和を計算しておきます。 累積和配列を \(S\) とすると、 \(S[i] = A_1 + A_2 + \cdots + A_i\)（ \(S[0] = 0\) ）となり、第 \(l\) 日から第 \(r\) 日までの和は \(S[r] - S[l-1]\) で \(O(1)\) で求められます。

具体的な手順は以下の通りです（0-indexed で説明します）。

1. \(M = T / C\) を計算する。
2. 累積和配列 \(S\) を作成する（ \(S[i] = \sum_{j=0}^{i-1} A[j]\) ）。
3. 左端 \(i\) を \(0\) から \(N-K\) まで順に動かす。
4. 右端のポインタ \(R\) を、前回の位置（または最小日数を満たす \(i+K\) ）からスタートし、 \(S[R] - S[i] \leq M\) を満たす限り右に進める。
5. ループを抜けたとき、 \(R-1\) が条件を満たす最大の右端（ \(max\_r\) ）となる。
6. \(max\_r \geq i+K\) であれば、左端 \(i\) に対して条件を満たす右端は \(i+K\) から \(max\_r\) までのすべての整数である。よって、その個数 \(max\_r - (i+K) + 1\) を答えに加算する。

計算量

• 時間計算量: \(O(N)\) 累積和の構築に \(O(N)\) かかります。尺取り法の部分では、左端の変数 \(i\) も右端の変数 \(R\) もそれぞれ \(0\) から \(N\) まで減少することなく単調に増加するため、内側の while ループが実行される回数は全体を通して高々 \(N\) 回です。したがって、全体の時間計算量は \(O(N)\) となり、制約下で十分に高速に動作します。

• 空間計算量: \(O(N)\) 入力配列 \(A\) と累積和配列 \(S\) を保持するために、 \(O(N)\) のメモリを使用します。

実装のポイント

• オーバーフローへの対策: 答え（条件を満たす組の個数）は最大で \(O(N^2)\) 通り（最大で約 \(2 \times 10^{12}\)）になります。これは 32 ビット整数型（C++の int）の最大値（約 \(2 \times 10^9\)）を大きく超えるため、答えを格納する変数 ans は必ず 64 ビット整数型（C++の long long）を使用してください。

• 除算の順序: \(C \times \text{区間和} \leq T\) をそのまま計算すると、 \(C\) や区間和が大きいため 64 ビット整数であってもオーバーフローする危険があります。あらかじめ \(M = T / C\) を計算しておくことで、オーバーフローを安全に回避できます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

    int N;
    long long C, T, K;
    if (!(cin >> N >> C >> T >> K)) return 0;

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    long long M = T / C;

    vector<long long> S(N + 1, 0);
    for (int i = 0; i < N; ++i) {
        S[i + 1] = S[i] + A[i];
    }

    long long ans = 0;
    long long R = 0;
    for (int i = 0; i <= N - K; ++i) {
        R = max(R, i + K);
        while (R <= N && S[R] - S[i] <= M) {
            R++;
        }
        long long max_r = R - 1;
        if (max_r >= i + K) {
            ans += max_r - (i + K) + 1;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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