Overview

A problem where you lower a tree by sinking it into the ground to reduce the height of apples, maximizing the number of apples that can be harvested by stretching alone.

Analysis

Key Points of the Problem

• Takahashi can reach up to \(T + K\) centimeters by stretching.
• Each apple is at height \(H_i\), and the entire tree can be sunk by at most \(D\) centimeters.
• After sinking, the height of each apple becomes \(H_i - D\), and the constraint \(H_i - D \geq 1\) must be satisfied for all apples.
• The goal is to maximize the number of apples that can be harvested by stretching alone.

Important Observations

• Sinking the tree lowers all apples by the same amount, so the relative height relationships do not change.
• The larger the sinking depth \(D\), the more apples at higher positions become harvestable.
• However, the lowest apple must not be buried underground, so the upper limit of \(D\) is \(\min(H) - 1\).
• For each apple, we can determine the “minimum \(D\) required for harvesting,” and if it is within the upper limit of \(D\), the apple can be harvested.

Naive Approach and Its Issues

• Exhaustively searching \(D\) from 0 to \(\min(H) - 1\) is impractical (requiring computations on the order of \(10^9\)).
• However, by determining whether each apple is harvestable based on the “minimum required \(D\),” exhaustive search becomes unnecessary.

Solution

• For each apple at height \(H_i\), the minimum \(D\) required for harvesting is \(\max(0, H_i - (T + K))\).
• If that \(D\) is within the allowable range (\(\leq \min(H) - 1\)), the apple can be harvested.
• We simply check this for all apples.

Algorithm

1. Read the input and compute \(T + K\) (the maximum reachable height).
2. Find the height of the lowest apple \(\min(H)\) and compute the upper limit of sinking depth \(D_{\text{max}} = \min(H) - 1\).
3. For each apple at height \(H_i\), compute the minimum required sinking amount: $\( D_{\text{required}} = \max(0, H_i - (T + K)) \)$
4. If \(D_{\text{required}}\) is at most \(D_{\text{max}}\), that apple can be harvested.
5. Count and output the number of harvestable apples.

Complexity

• Time complexity: \(O(N)\)
  (Each apple is evaluated in constant time)
• Space complexity: \(O(1)\)
  (Memory usage beyond input data is constant)

Implementation Notes

• sys.stdin.read is used for fast input.

• Since the required \(D\) is computed directly for each \(H_i\), sorting and binary search are unnecessary.

• Care must be taken so that the upper limit of \(D\) does not become negative (\(D = \max(0, \min(H) - 1)\)).

  Source Code

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()

This editorial was generated by qwen3-coder-480b.