概要

木を沈めることでりんごの高さを下げ、背伸びだけで収穫できるりんごの個数を最大化する問題。

考察

問題のポイント

• 高橋君は背伸びして最大 \(T + K\) センチメートルまで手が届く。
• 各りんごの高さは \(H_i\) で、木全体を最大 \(D\) センチ沈めることができる。
• 沈めた後のりんごの高さは \(H_i - D\) になり、すべての \(H_i - D \geq 1\) を満たす必要がある。
• 目標は背伸びだけで取れるりんごの個数を最大化すること。

重要な観察

• 木を沈めるとすべてのりんごが同じだけ下がるため、相対的な高さの関係は変わらない。
• 沈める深さ \(D\) を大きくすればするほど、より高いところにあるりんごも収穫可能になる。
• ただし、最も低いりんごが地面に埋まってしまってはいけないので、\(D\) の上限は \(\min(H) - 1\)。
• 各りんごについて「収穫するために最低限必要な \(D\)」を求めることができ、それが \(D\) の上限以内であれば収穫可能。

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

• \(D\) を 0 から \(\min(H) - 1\) まで全探索するのは非現実的（\(10^9\)オーダーの計算が必要）。
• しかし、各りんごが収穫可能かどうかを「必要な \(D\) の最小値」に基づいて判定すれば、全探索は不要。

解決策

• 各りんごの高さ \(H_i\) に対して、収穫に必要な最小の \(D\) は \(\max(0, H_i - (T + K))\)。
• その \(D\) が許容範囲（\(\leq \min(H) - 1\)）に入っていれば収穫可能。
• これをすべてのりんごに対して調べればよい。

アルゴリズム

1. 入力を読み込み、\(T + K\)（手が届く最大高さ）を計算。
2. 最も低いりんごの高さ \(\min(H)\) を求め、沈める深さの上限 \(D_{\text{max}} = \min(H) - 1\) を計算。
3. 各りんごの高さ \(H_i\) に対して、収穫に必要な最小の沈降量： $\( D_{\text{required}} = \max(0, H_i - (T + K)) \)$ を計算。
4. その \(D_{\text{required}}\) が \(D_{\text{max}}\) 以下であれば、そのりんごは収穫可能。
5. 収穫可能な個数をカウントして出力。

計算量

• 時間計算量: \(O(N)\)
  （各りんごに対して定数時間で判定を行う）
• 空間計算量: \(O(1)\)
  （入力データ以外の使用メモリは定数）

実装のポイント

• 入力の高速化のために sys.stdin.read を使っている。
• 各 \(H_i\) に対して直接必要な \(D\) を求めているため、ソートや二分探索は不要。
• \(D\) の上限が負にならないよう注意（\(D = \max(0, \min(H) - 1)\)）。

ソースコード

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    T = int(data[1])
    K = int(data[2])
    H = list(map(int, data[3:]))

    max_reach = T + K

    # 最も低いりんごの高さ
    min_h = min(H)

    # 沈める最大の深さ D の上限（min_h - (D) >= 1 すなわち D <= min_h - 1）
    max_d = min_h - 1
    if max_d < 0:
        max_d = 0

    # 収穫できるりんごの最大数を求める
    # D を 0 から max_d まで全探索は無理なので、二分探索する
    # 条件：H[i] - D <= T + K  → H[i] <= T + K + D
    # 収穫できる個数 = H[i] <= T + K + D である i の個数
    # さらに D <= max_d が必要

    # H をソートしておく
    H.sort()

    # D の最大値は max_d
    # D を固定すると、収穫できるりんごは H[i] <= T + K + D であるもの
    # つまり H[i] - (T + K) <= D なる i の個数
    # D >= H[i] - (T + K) なる i の個数
    # D >= max(0, H[i] - (T + K)) かつ D <= max_d

    # 各 H[i] に対して、必要な最小の D は max(0, H[i] - (T + K))
    # そのような D が max_d 以下であればカウントできる

    # 各 H[i] について、収穫可能か判定: H[i] <= T + K + D かつ D <= max_d かつ D >= 0
    # H[i] <= T + K + D → D >= H[i] - (T + K)
    # 必要な最小 D = max(0, H[i] - (T + K))
    # この D が <= max_d なら OK

    count = 0
    for h in H:
        required_d = max(0, h - max_reach)
        if required_d <= max_d:
            count += 1

    print(count)

if __name__ == "__main__":
    main()

---

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