概要

本問題は、長さ \(N\) の数列 \(A\) から、「長さが \(K\) 以上」かつ「要素の総和に \(C\) を掛けた値が \(T\) 以下」となるような連続部分列（区間）の個数を求める問題です。

考察

条件の整理

問題文の条件式は以下のように表されます。 $\(C \times (A_l + A_{l+1} + \cdots + A_r) \leq T\)$

\(C \geq 1\) であるため、両辺を \(C\) で割ることで、以下のように変形できます。 $\(A_l + A_{l+1} + \cdots + A_r \leq \left\lfloor \frac{T}{C} \right\rfloor\)$

ここで \(M = \left\lfloor \frac{T}{C} \right\rfloor\) とおくと、条件は「区間の総和が \(M\) 以下であること」と非常にシンプルになります。なお、 \(M = 0\) の場合は \(A_i \geq 1\) より条件を満たす区間は絶対に存在しません。

素朴なアプローチとその限界

すべての有効な区間 \((l, r)\) を全探索することを考えます。 \(1 \leq l \leq r \leq N\) かつ \(r - l + 1 \geq K\) を満たすペア \((l, r)\) をすべて調べると、区間の数は最悪で \(O(N^2)\) 個存在します。 本問題の制約は \(N \leq 2 \times 10^6\) であるため、 \(O(N^2)\) のアルゴリズムでは実行時間制限に間に合いません。

単調性の活用と「尺取り法」

数列の要素 \(A_i\) はすべて正（ \(A_i \geq 1\) ）です。このため、区間を右に広げる（ \(r\) を増やす）と総和は必ず増加し、左を削る（ \(l\) を増やす）と総和は必ず減少するという単調性があります。

この性質を利用すると、尺取り法（Two Pointers）を適用できます。 左端 \(l\) を固定したとき、条件（総和が \(M\) 以下）を満たす最大の右端を \(r\) とします。 このとき、左端を \(l\) から \(l+1\) に進めると、区間の総和は減少するため、新しく条件を満たす最大の右端は現在の \(r\) 以上の位置に存在することが保証されます。 したがって、右端 \(r\) を左に戻す必要はなく、常に右に進めるだけで探索が可能です。

アルゴリズム

各左端 \(l\) に対して、条件を満たす最大の右端 \(r\) を尺取り法で求めます。

1. \(M = \lfloor T / C \rfloor\) を計算します。 \(M = 0\) または \(N < K\) の場合は、満たす区間は存在しないため 0 を出力して終了します。
2. 左端 \(l\) を \(0\) から \(N - K\) まで順に動かします。
3. 各 \(l\) について、現在の区間和に \(A_{r+1}\) を加えても \(M\) 以下である限り、右端 \(r\) を右に進め、区間和を更新し続けます。
   • 初期状態（\(l=0\)）では、最小の長さ \(K\) を確保するため、 \(r = K-1\) とし、区間和を \(A_0 + \cdots + A_{K-1}\) に設定しておきます。
4. \(r\) を限界まで伸ばしたとき、区間和が \(M\) 以下であれば、 \(l\) を始点とする長さ \(K\) 以上の有効な区間の終点は \(l + K - 1\) から \(r\) までのすべてとなります。
   • このような終点の個数は \(r - (l + K - 1) + 1 = r - l - K + 2\) 個であり、これを答えに加算します。
5. 次のステップ（左端を \(l+1\) に進める）の準備として、区間和から \(A_l\) を引きます。
6. もし \(r\) が次の最小区間長を満たす位置（\(l + 1 + K - 1\)）未満になってしまった場合は、 \(r\) を右に \(1\) つ進めて区間和を更新します。

計算量

• 時間計算量: \(O(N)\) 左端のポインタ \(l\) も右端のポインタ \(r\) も、それぞれ最大で \(N\) 回しか右に進みません。各ステップの処理は \(O(1)\) で行われるため、全体の計算量は \(O(N)\) となり、 \(N \leq 2 \times 10^6\) でも実行時間制限に余裕で間に合います。
• 空間計算量: \(O(N)\) 入力された配列 \(A\) を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 区間和の差分更新: 毎ループで区間の和を \(O(N)\) かけて再計算すると全体の計算量が \(O(N^2)\) に悪化します。ポインタの移動に合わせて、加わる要素を足し、抜ける要素を引くことで、区間和を \(O(1)\) で維持しています。

• コーナーケースの処理: \(M = 0\) や \(N < K\) の場合、尺取り法のメインループに入る前に早期リターンすることで、配列の範囲外アクセスや無駄な計算を防いでいます。

  ソースコード

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    C = int(input_data[1])
    T = int(input_data[2])
    K = int(input_data[3])

    A = list(map(int, input_data[4:]))

    M = T // C
    if M == 0 or N < K:
        print(0)
        return

    cur_sum = sum(A[:K])
    ans = 0
    r = K - 1

    for l in range(N - K + 1):
        while r + 1 < N and cur_sum + A[r + 1] <= M:
            r += 1
            cur_sum += A[r]

        if cur_sum <= M:
            ans += r - l - K + 2

        cur_sum -= A[l]
        if r < l + K:
            if r + 1 < N:
                r += 1
                cur_sum += A[r]
            else:
                break

    print(ans)


if __name__ == "__main__":
    solve()

---

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