概要

\(N\) 日間の練習強度のデータから、「期間が \(K\) 日以上」かつ「合計強度が \(M\) 以上」という 2 つの条件を満たす区間 \((l, r)\) の個数を求める問題です。

考察

素朴な方法とその限界

すべての区間 \((l, r)\) を全探索することを考えます。区間の選び方は約 \(\frac{N^2}{2}\) 通りあり、各区間の合計を計算するのに最悪 \(O(N)\) かかるとすると、全体の計算量は \(O(N^3)\) となります。累積和を使えば合計の計算は \(O(1)\) になりますが、それでも \(O(N^2)\) です。 本問題では \(N = 2 \times 10^5\) であるため、\(N^2 = 4 \times 10^{10}\) となり、制限時間内に計算が終わりません。より効率的な \(O(N)\) や \(O(N \log N)\) のアプローチが必要です。

単調性の利用

この問題の重要なポイントは、「練習強度 \(A_i\) がすべて正（\(1\) 以上）である」 という点です。 これにより、区間の左端 \(l\) を固定したとき、右端 \(r\) を右に動かすほど区間の合計値は必ず増加します。

もし、ある区間 \([l, r]\) が条件（合計 \(\geq M\) かつ 長さ \(\geq K\)）を満たした場合、それより右端を伸ばした区間 \([l, r+1], [l, r+2], \dots, [l, N]\) もすべて条件を満たすことになります。 したがって、各 \(l\) に対して 「条件を満たす最小の \(r\)」 を効率よく見つけることができれば、その \(l\) を左端とする条件を満たす区間の数は \((N - r + 1)\) 個であると一気に計算できます。

アルゴリズム

1. 累積和の構築

区間 \([l, r]\) の合計を高速に求めるため、累積和配列 \(S\) を用意します。 - \(S[0] = 0\) - \(S[i] = A_1 + A_2 + \cdots + A_i\) これを用いると、\(A_l + \cdots + A_r = S[r] - S[l-1]\) と計算できます。

2. 尺取り法（ツーポインタ）

左端 \(l\) を \(1\) から順に動かしていき、それに合わせて右端の候補 \(r\_ptr\) を動かします。 1. 合計値の条件: \(S[r] - S[l-1] \geq M\) 、つまり \(S[r] \geq S[l-1] + M\) を満たす最小の \(r\) を \(r\_ptr\) とします。\(A_i > 0\) なので、 \(l\) が増えれば \(r\_ptr\) も右にしか移動しません。 2. 長さの条件: 区間の長さが \(K\) 以上であるためには \(r \geq l + K - 1\) が必要です。 3. 条件の統合: 上記 2 つを同時に満たす最小の右端 \(r_{start}\) は、\(\max(r\_ptr, l + K - 1)\) となります。

この \(r_{start}\) が \(N\) 以下であれば、右端として \(r_{start}, r_{start}+1, \dots, N\) のすべてが選べるため、\((N - r_{start} + 1)\) を答えに加算します。

計算量

• 時間計算量: \(O(N)\)
  • 累積和の計算に \(O(N)\) かかります。
  • 尺取り法の部分では、左端 \(l\) と右端 \(r\_ptr\) がそれぞれ最大 \(N\) 回ずつしか移動しないため、\(O(N)\) です。
• 空間計算量: \(O(N)\)
  • 長さ \(N+1\) の累積和配列を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 大きな値の処理: 合計値 \(M\) は最大 \(10^{14}\) に達するため、プログラミング言語によっては 64 ビット整数型（Python では標準の整数型で OK）を使用する必要があります。

• 高速な入出力: \(N\) が \(2 \times 10^5\) と大きいため、Python では sys.stdin.read().split() などを用いて一括で入力を読み込むと実行時間を短縮できます。

• 境界条件: \(l\) の範囲は、長さ \(K\) 以上の区間が作れる \(N-K+1\) までとなります。

  ソースコード

import sys

def solve():
    # 標準備入力をすべて読み込み、空白で分割してリスト化します。
    # 大規模な入力に対して効率的に処理するための手法です。
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 入力値の取得
    N = int(input_data[0])
    K = int(input_data[1])
    M = int(input_data[2])
    # A_1, A_2, ..., A_N を 0-indexed のリストとして保持します。
    A = list(map(int, input_data[3:]))
    
    # 累積和の計算
    # S[i] は最初の i 日間の練習強度の合計 (A_1 + ... + A_i) を表します。
    # S[0] = 0 とします。
    S = [0] * (N + 1)
    current_sum = 0
    for i in range(N):
        current_sum += A[i]
        S[i+1] = current_sum
        
    ans = 0
    r_ptr = 1
    
    # 各開始日 l に対して、条件を満たす終了日 r の個数を数えます。
    # 連続する日数が K 以上である必要があるため、l は最大で N - K + 1 までとなります。
    for l in range(1, N - K + 2):
        # 目標とする累積和の値： S[r] - S[l-1] >= M  =>  S[r] >= S[l-1] + M
        target = S[l-1] + M
        
        # 練習強度の合計が M 以上になる最小の r を尺取り法（二つのポインタ）で探します。
        # A_i >= 1 より累積和 S は単調増加するため、r_ptr を戻す必要はありません。
        while r_ptr <= N and S[r_ptr] < target:
            r_ptr += 1
        
        # 条件1: 合計が M 以上 (r >= r_ptr)
        # 条件2: 期間の長さが K 以上 (r - l + 1 >= K  => r >= l + K - 1)
        # これら両方を満たす最小の r を求めます。
        actual_r_start = max(r_ptr, l + K - 1)
        
        # 最小の r が期間内 (N以下) であれば、それ以降のすべての r も条件を満たします。
        if actual_r_start <= N:
            # 終了日 r として選べるのは [actual_r_start, N] の範囲の整数です。
            ans += (N - actual_r_start + 1)
    
    # 結果の出力
    print(ans)

if __name__ == '__main__':
    solve()

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