概要

全てのりんごの高さを一律に \(D\) だけ下げられるとき、制約 \(H_i-D\ge 1\) を満たしつつ、背伸びだけで届く（\(H_i-D\le T+K\)）りんごの個数を最大化します。

考察

りんごを \(D\) cm 沈めた後、\(i\) 番目のりんごが背伸びだけで取れる条件は \( H_i - D \le T+K \) です。これを変形すると \( H_i \le T+K+D \) となり、「元の高さ \(H_i\) がしきい値 \(T+K+D\) 以下なら取れる」と読み替えられます。

ここで重要な観察は次の2点です。

• \(D\) を大きくすると（より深く沈めると）取れるりんごは減らない
  しきい値 \(T+K+D\) が大きくなるので、条件 \(H_i \le T+K+D\) を満たすりんごは単調に増えます（同じか増える）。

• \(D\) には上限がある
  「最も低いりんごが 1cm 未満にならない」より、全ての \(i\) で \(H_i-D\ge 1\)、特に最小値 \(m=\min(H)\) について \( m - D \ge 1 \Rightarrow D \le m-1 \) です。つまり 取りうる最大の沈め量は \(D_{\max}=m-1\) です。

以上より、取れる個数は \(D\) を増やすほど（単調に）増えるので、最適解は常に \(D=D_{\max}=m-1\) を選ぶことになります。

素朴に「\(D\) を全探索」すると、\(D\) の範囲が最大で \(10^9\) になり得て現実的ではありませんが、上の単調性により全探索は不要です。

具体例：\(H=[3,10],\ T+K=7\) のとき

• \(D=0\): 取れるのは \(3\) のみ（1個）
  
• 最大 \(D=m-1=2\): 高さは \([1,8]\) になり、\(1\) は取れるが \(8\) は不可（やはり1個）
  別の例で \(H=[5,6,10],\ T+K=7\)
  
• \(D=0\): 取れるのは \(5,6\)（2個）
  
• \(D=4\)（最大、\(m=5\)なので \(m-1=4\)）: しきい値は \(7+4=11\)、元の高さで \(11\) 以下が全てなので3個取れる。

アルゴリズム

1. 配列 \(H\) の最小値 \(m=\min(H)\) を求める。
2. 沈められる最大値を \(D=m-1\) とする。
3. 背伸びで取れる条件 \(H_i \le T+K+D\) を満たす要素数を数える。
4. その個数を出力する。

計算量

• 時間計算量: \(O(N)\)（最小値の計算と個数カウントで各1回ずつ走査）
• 空間計算量: \(O(N)\)（入力配列 \(H\) を保持）

実装のポイント

• 上限の沈め量は必ず \(D=\min(H)-1\)（負にならない：\(H_i\ge 1\) より \(D\ge 0\) が保証される）。
• 判定は「沈めた後」を直接計算してもよいですが、オーバーフロー等を避けるためにも式を変形して \(H_i \le T+K+D\) として数えるのが簡潔です。

ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, T, K = map(int, input().split())
    H = list(map(int, input().split()))
    m = min(H)
    D = m - 1  # maximum possible lowering
    limit = T + K + D
    ans = sum(1 for h in H if h <= limit)
    print(ans)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。