概要

数列の連続する部分列のうち、長さが \(K\) 以上であり、要素の合計が \(\lfloor T/C \rfloor\) 以下であるものの個数を求める問題です。

考察

まず、読書時間の条件である \(C \times (A_l + \cdots + A_r) \le T\) は、両辺を \(C\) で割ることで \(A_l + \cdots + A_r \le \lfloor T/C \rfloor\) と言い換えることができます。

この問題で重要なのは、各日のページ数 \(A_i\) がすべて \(1\) 以上であるという点です。これにより、「区間を長くすればするほど、ページ数の合計は必ず大きくなる（単調増加する）」という性質が成り立ちます。

すべての区間 \((l, r)\) の組み合わせを全探索すると、状態数が \(O(N^2)\) となり、制約の \(N \le 2 \times 10^6\) では実行時間制限（TLE）に引っかかってしまいます。 しかし、上記の「単調性」を利用すると、ある左端 \(l\) に対して条件を満たすギリギリの右端 \(r\) を見つけたとき、それより短い区間もすべて条件を満たすことが分かります。また、左端 \(l\) を右にずらすと、合計値が減るため、右端 \(r\) は以前の位置からさらに右に進める（あるいはそのまま留まる）ことになります。 このように、左右の端を一方通行で進めていく「しゃくとり法（Two Pointers）」を用いることで、計算量を大幅に削減できます。

アルゴリズム

1. 許容される合計ページ数の上限 \(M = \lfloor T/C \rfloor\) を計算します。
2. しゃくとり法を用いて、左端 \(l\) を \(0\) から \(N-1\) まで順に調べます。
3. 現在の区間 \([l, r)\) （\(l\) 番目から \(r-1\) 番目まで）の和 current_sum に、次の要素 \(A_r\) を足しても \(M\) 以下である限り、右端 \(r\) を右へ進めます。
4. \(r\) を限界まで進めたとき、条件を満たす最大の区間は \([l, r)\) となります。 このとき、長さを \(K\) 以上にするための右端のインデックスを \(x\) （\(l \le x < r\)）とすると、区間の長さ \(x - l + 1 \ge K\) より、\(x \ge l + K - 1\) を満たす必要があります。 条件を満たす \(x\) の範囲は \(l + K - 1 \le x \le r - 1\) となるため、その個数は \((r - 1) - (l + K - 1) + 1 = r - l - K + 1\) 個です。これを答えに加算します。
5. 次の \(l\) に進む準備として、current_sum から \(A_l\) を引きます。ただし、そもそも \(A_l > M\) などの理由で \(r = l\) となっていた場合は、引くべき要素がないため \(r\) を \(1\) つ進めるだけにします。

計算量

• 時間計算量: \(O(N)\) 左端 \(l\) は \(0\) から \(N-1\) まで \(1\) ずつ増加し、右端 \(r\) も \(0\) から最大 \(N\) まで一方通行でしか増加しません。したがって、内側の while ループは全体を通しても高々 \(N\) 回しか実行されず、全体の計算量は \(O(N)\) となります。
• 空間計算量: \(O(N)\) 長さ \(N\) の数列 \(A\) を配列としてメモリ上に保持するため、\(O(N)\) の空間を消費します。

実装のポイント

• 整数除算の利用: \(T / C\) を浮動小数点数（小数）で計算すると、値が非常に大きい場合に精度誤差が生じ、誤った判定をしてしまう可能性があります。Pythonでは必ず // 演算子を用いて、正確に切り捨ての整数除算を行いましょう。

• しゃくとり法のコーナーケース: \(A_l > M\) のとき、区間内に \(1\) つも要素を含めることができず \(r = l\) となります。このとき current_sum から \(A_l\) を引いてしまうと、合計値がマイナスになり以降の計算がおかしくなってしまいます。そのため、if r == l: の分岐を入れて、\(r\) だけを強制的に進める処理を忘れないようにすることが重要です。

  ソースコード

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])
    
    M = T // C
    
    A = list(map(int, input_data[4:]))
    
    ans = 0
    r = 0
    current_sum = 0
    
    for l in range(N):
        while r < N and current_sum + A[r] <= M:
            current_sum += A[r]
            r += 1
        
        if r - l >= K:
            ans += r - l - K + 1
            
        if r == l:
            r += 1
        else:
            current_sum -= A[l]
            
    print(ans)

if __name__ == '__main__':
    solve()

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