概要

連続する \(K\) 日以上の期間 \((l, r)\) のうち、合計読書時間が制限時間 \(T\) 以下となるものの個数を数える問題です。累積和と尺取り法（Two Pointers）を組み合わせて効率的に解きます。

考察

素朴なアプローチ

全ての組 \((l, r)\) を二重ループで調べると \(O(N^2)\) 個の組があり、\(N \leq 2 \times 10^6\) では間に合いません。

重要な観察

\(A_i \geq 1\) であるため、累積和 \(\text{prefix}[i]\) は狭義単調増加です。つまり、\(l\) を固定したとき、\(r\) を大きくするほど区間の合計 \(\text{prefix}[r] - \text{prefix}[l-1]\) は単調に増加します。

これにより、各 \(l\) に対して「条件を満たす最大の \(r\)」が一意に定まります。さらに、\(l\) を \(1\) 増やすと \(\text{prefix}[l-1]\) が増加するため、引かれる量が大きくなり、条件が緩くなります。よって、最大の有効な \(r\) は \(l\) の増加に対して減少しません。

この単調性から尺取り法が適用できます。

アルゴリズム

1. 累積和の構築: \(\text{prefix}[i] = A_1 + A_2 + \cdots + A_i\) を計算する。

2. 条件の整理: 条件 \(C \times (A_l + \cdots + A_r) \leq T\) は、\(\text{prefix}[r] - \text{prefix}[l-1] \leq \lfloor T / C \rfloor\) と同値です（全て正の整数のため）。\(\text{max\_sum} = \lfloor T / C \rfloor\) とおきます。

3. 尺取り法: 右端ポインタ right を管理しながら、\(l = 1, 2, \ldots, N\) について以下を行います：

   • right を \(\max(\text{right}, l + K - 1)\) に更新（最低 \(K\) 日の制約）。
   • right > N なら、この \(l\) では有効な区間がないのでスキップ。
   • 最小の有効な \(r = l + K - 1\) で条件を満たさなければスキップ。
   • 条件を満たす限り right を右に伸ばす。
   • 有効な \(r\) の範囲は \([l+K-1, \text{right}]\) なので、答えに \(\text{right} - (l+K-1) + 1\) を加算。

具体例: \(N=5, K=2, C=1, T=10, A=[3,2,1,4,5]\) の場合 - \(l=1\): 合計が \(10\) 以下となる最大の \(r\) は \(4\)（合計 \(3+2+1+4=10\)）。有効範囲は \(r \in [2,4]\) → 3個 - \(l=2\): 最大の \(r\) は \(4\)（合計 \(2+1+4=7\)）。有効範囲は \(r \in [3,4]\) → 2個 - \(l=3\): 最大の \(r\) は \(5\)（合計 \(1+4+5=10\)）。有効範囲は \(r \in [4,5]\) → 2個 - \(l=4\): 合計 \(4+5=9 \leq 10\)。有効範囲は \(r \in [5,5]\) → 1個

合計: 8個

計算量

• 時間計算量: \(O(N)\)（尺取り法により right は合計で最大 \(N\) 回しか進まない）
• 空間計算量: \(O(N)\)（累積和配列の分）

実装のポイント

• オーバーフロー対策: \(C\) と合計ページ数の積が大きくなりうるが、条件を \(\text{prefix}[r] - \text{prefix}[l-1] \leq \lfloor T/C \rfloor\) に変換することで、大きな掛け算を避けている。

• right の初期化: \(l\) が増加しても right をリセットしない（単調性を利用）。ただし right < l + K - 1 の場合は \(l + K - 1\) まで引き上げる必要がある。

• 高速入力: \(N\) が最大 \(2 \times 10^6\) と大きいため、sys.stdin.buffer.read() で一括読み込みしている。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    C = int(input_data[1])
    T = int(input_data[2])
    K = int(input_data[3])
    A = [int(input_data[4 + i]) for i in range(N)]
    
    # prefix sum
    prefix = [0] * (N + 1)
    for i in range(N):
        prefix[i + 1] = prefix[i] + A[i]
    
    # We need to count pairs (l, r) with 1 <= l <= r <= N, r - l + 1 >= K,
    # and C * (prefix[r] - prefix[l-1]) <= T
    # i.e., prefix[r] - prefix[l-1] <= T // C (integer division, but careful with floor)
    
    # Since A_i >= 1, the sum is monotonically increasing as r increases for fixed l.
    # We can use two pointers / sliding window approach.
    
    # For each l, find the maximum r such that C * (prefix[r] - prefix[l-1]) <= T
    # and r >= l + K - 1
    # The sum prefix[r] - prefix[l-1] is increasing in r.
    
    # threshold for sum: S <= T / C
    # Since all values are integers, S <= floor(T / C)
    max_sum = T // C
    
    count = 0
    # Two pointer: for each l (1-indexed), find max r such that prefix[r] - prefix[l-1] <= max_sum
    # Then valid r range is [l+K-1, max_r] if l+K-1 <= max_r
    
    right = 0  # right will track the furthest r (1-indexed) we can go
    # Actually, let's use a simpler two-pointer where we iterate l from 1 to N
    
    for l in range(1, N + 1):
        # We need prefix[r] - prefix[l-1] <= max_sum
        # Start right from max(right, l+K-1 - 1) ... but we need to be careful
        # Actually since prefix is non-decreasing (A_i >= 1), as l increases,
        # the maximum valid r can only increase or stay (since prefix[l-1] increases).
        # Wait, no: as l increases, prefix[l-1] increases, so the constraint becomes easier,
        # meaning max valid r can increase. But we also need r >= l+K-1 which increases.
        
        # Let's just find max r for each l using the pointer that only moves forward.
        if right < l + K - 1:
            right = l + K - 1
        
        if right > N:
            # No valid r for this l
            continue
        
        # Check if even the minimum valid r is feasible
        if prefix[right] - prefix[l - 1] > max_sum:
            continue
        
        # Expand right as far as possible
        while right + 1 <= N and prefix[right + 1] - prefix[l - 1] <= max_sum:
            right += 1
        
        # Valid r: from l+K-1 to right
        count += right - (l + K - 1) + 1
    
    print(count)

main()

---

この解説は claude4.6opus-thinking によって生成されました。