概要

木を地面に沈めることで、できるだけ多くのりんごを背伸びだけで収穫できるようにする問題です。最適な沈める深さを求め、収穫可能なりんごの個数を数えます。

考察

重要な気づき

1. 沈める深さを大きくするほど有利

   • 木を深さ \(D\) だけ沈めると、すべてのりんごの高さが \(D\) だけ低くなります
   • りんごの高さが低くなれば、手が届きやすくなります
   • したがって、できるだけ深く沈めるのが最適です

2. 沈められる深さの制限

   • 制約「最も低いりんごの高さが \(1\) センチ未満になってはいけない」があります
   • 最も低いりんごの高さを \(H_{\min}\) とすると、\(H_{\min} - D \geq 1\) が必要
   • よって、\(D \leq H_{\min} - 1\) となり、最大で \(H_{\min} - 1\) だけ沈められます

3. 収穫できる条件

   • 手が届く最大の高さは \(T + K\) センチメートル
   • 深さ \(D\) で沈めた後、りんごの高さは \(H_i - D\)
   • 収穫できる条件: \(H_i - D \leq T + K\)、つまり \(H_i \leq T + K + D\)

具体例

例えば、\(T = 150\), \(K = 30\)（手が届く高さは \(180\) cm）、りんごの高さが \([100, 150, 200, 250]\) の場合：

• \(H_{\min} = 100\) なので、最大で \(D = 99\) まで沈められます
• 収穫できる条件: \(H_i \leq 180 + 99 = 279\)
• 高さ \(250\) 以下のりんごはすべて収穫可能 → 4個

アルゴリズム

1. りんごの高さ \(H\) を昇順にソートする
2. 最小の高さ \(H_{\min}\)（ソート後の先頭）を取得
3. 沈められる最大深さ \(D = \max(0, H_{\min} - 1)\) を計算
4. 手が届く高さの閾値 \(\text{threshold} = T + K + D\) を計算
5. ソート済み配列に対して二分探索で、\(H_i \leq \text{threshold}\) を満たすりんごの個数を数える

二分探索の活用

素朴に全てのりんごを一つずつ確認すると \(O(N)\) ですが、ソート済み配列では bisect_right を使うことで効率的に個数を数えられます。bisect_right(H, threshold) は、threshold 以下の要素の個数を返します。

計算量

• 時間計算量: \(O(N \log N)\)
  • ソートに \(O(N \log N)\)
  • 二分探索に \(O(\log N)\)
• 空間計算量: \(O(N)\)
  • りんごの高さを格納する配列

実装のポイント

1. \(D\) が負になる場合の処理

   • \(H_{\min} = 1\) のとき、\(H_{\min} - 1 = 0\) となり、沈められません
   • \(H_{\min} < 1\) は制約上ありえませんが、念のため max(0, max_D) としておくと安全です

2. オーバーフローに注意

   • \(T\), \(K\), \(H_i\) は最大 \(10^9\) なので、threshold = T + K + D は最大約 \(3 \times 10^9\)
   • Python では整数のオーバーフローを気にする必要はありませんが、他の言語では64ビット整数を使いましょう

3. ソート済み配列の最小値

   • ソート後は先頭要素 H[0] が最小値なので、わざわざ min() 関数を使う必要はありません

ソースコード

import bisect

def solve():
    N, T, K = map(int, input().split())
    H = list(map(int, input().split()))
    
    # ソートする
    H.sort()
    
    # 木を沈める深さDを考える
    # すべてのりんごについて H_i - D >= 1 を満たす必要がある
    # つまり D <= H_i - 1 for all i
    # よって D <= min(H) - 1
    
    min_H = H[0]  # ソート済みなので最小値は先頭
    max_D = min_H - 1  # 沈められる最大深さ
    
    # 手が届く高さは T + K
    reach = T + K
    
    # 深さDで沈めると、りんごの高さは H_i - D になる
    # H_i - D <= reach となるりんごを収穫できる
    # つまり H_i <= reach + D
    
    # Dは 0 から max_D まで選べる
    # D = max_D のとき、H_i <= reach + max_D を満たすりんごの数が最大になる
    # （Dを大きくするほど、より多くのりんごに手が届く可能性がある）
    
    # 最適な D は max_D（可能な限り深く沈める）
    # ただし max_D < 0 の場合は D = 0
    D = max(0, max_D)
    
    # H_i <= reach + D を満たすりんごの個数を数える
    threshold = reach + D
    
    # ソート済み配列で二分探索
    count = bisect.bisect_right(H, threshold)
    
    print(count)

solve()

この解説は claude4.5opus によって生成されました。