概要

\(N\) 個のりんごを、木を地面に沈めることでできるだけ多く収穫する問題です。木を沈める深さ \(D\) を適切に決めることで、手の届く範囲（高さ \(T+K\) 以下）に入るりんごの数を最大化します。

考察

1. 収穫できる条件を整理する

\(i\) 番目のりんごの元の高さを \(H_i\) とします。木を \(D\) センチメートル沈めたとき、りんごの高さは \(H_i - D\) になります。 高橋君の手が届く最大の高さは \(T+K\) なので、収穫できる条件は以下の不等式で表せます。 \(H_i - D \leq T + K\) これを \(H_i\) について整理すると、以下のようになります。 \(H_i \leq T + K + D\)

この式から、沈める深さ \(D\) が大きければ大きいほど、より高い位置にあるりんごに手が届くようになることが分かります。

2. 深さ \(D\) の限界を考える

問題文には「最も低い位置にあるりんごの高さが \(1\) センチメートル未満になってはいけない」という制約があります。 すべての \(i\) について \(H_i - D \geq 1\) を満たす必要があるため、これを \(D\) について整理すると： $\(D \leq H_i - 1\)\( これがすべてのりんごに対して成り立たなければならないため、\)D\( は「最も低いりんごの高さ \)- 1\(」以下である必要があります。 りんごの高さの最小値を \)H{\min}\( とすると、許容される \)D\( の最大値 \)D{\max}\( は次のようになります。 \)D{\max} = H{\min} - 1$

3. 最適な戦略

\(D\) を大きくするほど収穫できるりんごは増えるため、限界である \(D_{\max}\) を採用するのが最適です。 このとき、収穫できる条件は以下のようになります。 \(H_i \leq T + K + (H_{\min} - 1)\)

この条件を満たすりんごの個数を数えれば、それが答えとなります。

アルゴリズム

1. 全てのりんごの高さの中から最小値 \(H_{\min}\) を見つける。
2. 木を沈められる最大の深さ \(D_{\max} = H_{\min} - 1\) を計算する。
3. 高橋君が届く境界線 \(ReachLimit = T + K + D_{\max}\) を計算する。
4. 各りんごの高さ \(H_i\) について、\(H_i \leq ReachLimit\) を満たすものの個数をカウントする。

計算量

• 時間計算量: \(O(N)\)
  • りんごの高さの最小値を探すのに \(O(N)\)、条件を満たす個数を数えるのに \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • \(N\) 個のりんごの高さをリストに格納するために \(O(N)\) のメモリを使用します。

実装のポイント

• \(N\) が最大 \(2 \times 10^5\) と大きいため、Pythonでは sys.stdin.read().split() などを用いて高速に入力を読み込むのが効率的です。
• りんごの高さ \(H_i\) は最大 \(10^9\) と大きいため、計算過程で大きな数値（最大 \(3 \times 10^9\) 程度）を扱いますが、現代のプログラミング言語（Python含む）の整数型であれば問題なく扱えます。

ソースコード

import sys

def main():
    # 標準入力からすべてのデータを取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: りんごの個数
    # T: 高橋君の身長
    # K: 背伸びで届く追加の高さ
    N = int(input_data[0])
    T = int(input_data[1])
    K = int(input_data[2])
    
    # H: 各りんごの高さ
    H = list(map(int, input_data[3:]))
    
    # 木を沈める深さを D とすると、収穫条件は H_i - D <= T + K となる。
    # すなわち、H_i <= T + K + D を満たすりんごを収穫できる。
    # D を大きくするほど収穫できるりんごの個数は（単調に）増加するため、
    # 制約の範囲内で最大の D を選択するのが最適である。
    
    # 制約: すべての i について H_i - D >= 1
    # これより、D <= H_i - 1 がすべての i について成り立つ必要がある。
    # したがって、D の最大値 D_max は min(H_i) - 1 となる。
    H_min = min(H)
    D_max = H_min - 1
    
    # 最大の深さ D_max を用いたときの手が届く高さの境界
    reach_limit = T + K + D_max
    
    # 条件 H_i <= reach_limit を満たすりんごの個数をカウント
    ans = 0
    for h in H:
        if h <= reach_limit:
            ans += 1
            
    # 結果を出力
    print(ans)

if __name__ == '__main__':
    main()

---

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