概要

\(N\) 日間の練習強度が与えられ、連続する \(K\) 日以上で合計が \(M\) 以上になる区間の個数を数える問題。

考察

この問題では、すべての区間 \((l, r)\) に対して「長さが \(K\) 以上」かつ「合計が \(M\) 以上」であるかどうかを判定する必要があります。

素朴なアプローチとその問題点

まず思いつくのは、全通りの区間 \((l, r)\) を試す方法です。区間の合計を求めるために毎回和を計算すると、時間計算量は \(O(N^3)\) となり、\(N\) が最大 \(2 \times 10^5\) なので到底間に合いません。

たとえば以下のような入力があったとします：

N=5, K=2, M=5
A = [2, 2, 2, 2, 2]

この場合、\((l,r)=(1,2), (1,3), ..., (4,5)\) など、多くの区間が候補になりますが、それぞれの和を愚直に計算していたら時間がかかりすぎます。

改善策：累積和と二分探索

区間の和を高速に求めるには 累積和 を使うのが定石です。累積和配列 \(prefix\) を用意しておけば、任意の区間 \([l, r]\) の和は \(O(1)\) で求められます：

\[ \text{sum}(l, r) = prefix[r] - prefix[l-1] \]

次に、「条件を満たす区間」を効率よく数える必要があります。
固定された左端 \(l\) に対して、右端 \(r\) を動かしたときに区間和が初めて \(M\) 以上になる地点を見つけられれば、それ以降のすべての \(r\) も条件を満たすことになります。

つまり、各 \(l\) ごとに、以下の操作を行います： 1. 最小の区間長 \(K\) を満たす最初の右端 \(min\_r = l + K - 1\) を求める。 2. この範囲から \(N\) までの中で、初めて区間和が \(M\) 以上になる \(r\) を 二分探索 で探す。 3. そのような \(r\) があれば、そこから最後まで全部カウントに含める。

こうすることで、各区間の和を毎回計算せず、かつ全探索も避けられるので、効率的に答えを求めることができます。

アルゴリズム

1. 累積和配列 \(prefix\) を構築する（長さ \(N+1\)）。
2. 各左端 \(l = 1, 2, ..., N\) について以下を行う：
   • 必要最小限の区間長 \(K\) を満たす最初の右端 \(min\_r = l + K - 1\) を計算。
   • \(min\_r > N\) ならスキップ。
   • 二分探索により、区間和が \(M\) 以上になる最小の右端 \(valid\_r\) を求める。
   • そのような \(valid\_r\) が存在すれば、\(valid\_r\) から \(N\) までのすべての右端が条件を満たすので、個数 \(N - valid\_r + 1\) を加算する。

計算量

• 時間計算量: \(O(N \log N)\)
  • 各 \(l\) に対して二分探索を行うため、全体で \(O(N \log N)\)。
• 空間計算量: \(O(N)\)
  • 累積和配列のサイズが \(N+1\)。

実装のポイント

• 累積和は先頭に \(0\) を追加しておくと、添字処理が簡単になります。
• 二分探索では「初めて条件を満たす位置」を探すため、right = mid - 1 として更新します。
• prefix[l-1] の参照時に \(l=1\) でも安全にするために、prefix 配列のインデックスをずらして管理します。

ソースコード

import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    K = int(data[1])
    M = int(data[2])
    
    A = list(map(int, data[3:3+N]))
    
    # 累積和を計算
    prefix = [0] + list(accumulate(A))
    
    count = 0
    
    # 各開始位置 l について、条件を満たす終了位置 r の個数を数える
    for l in range(1, N+1):
        # 区間長が K 以上である最小の r
        min_r = l + K - 1
        if min_r > N:
            continue
        
        # 二分探索で条件を満たす最小の r を求める
        left = min_r
        right = N
        valid_r = -1
        
        while left <= right:
            mid = (left + right) // 2
            s = prefix[mid] - prefix[l-1]
            if s >= M:
                valid_r = mid
                right = mid - 1
            else:
                left = mid + 1
        
        # 条件を満たす r が存在すれば、それ以降すべての r も条件を満たす
        if valid_r != -1:
            count += N - valid_r + 1
            
    print(count)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。