概要

連続する高々 \(M\) 本の木からなる区間で、出荷基準 \(K\) 以上のかんづめができるりんごの総数を最大化する問題です。

考察

この問題では、ある連続した区間 \([L, R]\)（\(R - L + 1 \leq M\)）を選ぶことで、その区間に含まれる木のうち、\(H_i \geq K\) を満たす木からのみりんごを得ることができます。得られるりんごの数は、それらの木の \(H_i\) の合計になります。

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

最初に思いつくのは、すべての区間 \([L, R]\)（\(R - L + 1 \leq M\)）に対して、条件を満たす木のりんごの合計を計算することです。しかし、これは \(O(N \cdot M)\) の計算が必要となり、\(N\) と \(M\) が最大で \(10^6\) になるので、全体で \(10^{12}\) 回程度の計算が必要になり、時間内に終わりません（TLE）。

改善方法：累積和の活用

各区間の「出荷可能なりんごの合計」を高速に求めることができれば、全探索でも間に合います。そこで、事前に「出荷可能な木のりんごの数」だけを集めた配列を作り、その累積和を前もって計算しておくことで、任意の区間の合計を \(O(1)\) で求められるようにします。

つまり： - 各 \(H_i\) について、\(H_i \geq K\) ならそのまま、そうでなければ \(0\) とする配列 values を作る。 - この配列の累積和 acc を計算しておく。 - これにより、区間 \([L, R]\) の合計は acc[R+1] - acc[L] で求められる。

こうすることで、各区間の合計が \(O(1)\) で求められ、全体の計算量は \(O(N)\) になります。

アルゴリズム

1. 入力から \(N\), \(M\), \(K\) および \(H_i\) を受け取る。
2. 各 \(H_i\) について、\(H_i \geq K\) ならその値、そうでなければ \(0\) とした配列 values を作る。
3. values の累積和 acc を計算する（先頭に \(0\) を追加してインデックス操作を簡単にする）。
4. 各左端 \(L\)（0-indexed）について、区間長が最大 \(M\) になる右端 \(R = \min(L + M, N)\) を設定し、区間和を acc[R] - acc[L] で計算。
5. 最大の区間和を記録して出力。

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 累積和を計算する際に、先頭に \(0\) を追加しておくと、区間 \([L, R)\) の和が acc[R] - acc[L] で自然に計算できて便利です。

• 区間の終端の扱いに注意してください。Pythonのスライスやインデックス指定では、範囲外アクセスを防ぐために min() を使って上限を抑えています。

  ソースコード

import sys
from itertools import accumulate

def main():
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    H = list(map(int, data[3:3+N]))
    
    # 各木について、出荷可能ならその個数、不可なら0
    values = [h if h >= K else 0 for h in H]
    
    # 累積和を計算
    acc = [0] + list(accumulate(values))
    
    max_apples = 0
    
    # 区間[L, R] (1-indexed) に対応する 0-indexed の範囲は [L-1, R]
    # 区間長が最大Mなので、R - L + 1 <= M → R <= L + M - 1
    for L in range(N):
        R_end = min(L + M, N)
        # 区間 [L, R_end) の和 = acc[R_end] - acc[L]
        current_sum = acc[R_end] - acc[L]
        if current_sum > max_apples:
            max_apples = current_sum
            
    print(max_apples)

if __name__ == "__main__":
    main()

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