概要

\(N\) 個の教室の老朽度のうち、最大 \(M\) 個を \(0\) に変更できるとき、変更後の老朽度の最大値を最小にする問題。

考察

この問題では、新しいエアコンを最大 \(M\) 台設置でき、それによって教室の老朽度を \(0\) にできます。目標は「全ての教室の老朽度の最大値」をできるだけ小さくすることです。

素朴な方法として、「老朽度の大きい方から \(M\) 個を \(0\) にする」と考えたくなります。しかし、それだと最適でないことがあります。例えば、老朽度が [100, 90, 10] で \(M=1\) の場合、最大値を \(90\) にできるのに、単純に最大を \(0\) にすると最大値が \(100\) になってしまいます。

そこで重要な観察があります： - 「最終的な老朽度の最大値を \(x\) 以下にできるか？」という判定問題を考えると、これは効率的に解けます。 - 老朽度が \(x\) より大きい教室には、必ず新しいエアコンを設置する必要があります。 - そのような教室の数が \(M\) 以下であれば、達成可能です。

このような「最大値の最小化」の問題では、二分探索が非常に有効です。探索範囲は \(0\) から \(\max(D_i)\) までで、ある値 \(x\) に対して条件を満たすかどうかを判定すればよいのです。

アルゴリズム

1. 老朽度のリスト \(D\) を降順にソートします（大きい順）。
2. 二分探索で「最終的な老朽度の最大値」の最小値を求めます。
3. 各ステップで、ある値 \(x\) を「達成可能かどうか」判定します。
   • \(D_i > x\) となる教室の数をカウントし、それが \(M\) 以下であれば達成可能。
4. 二分探索の結果、達成可能な最小の最大値を出力します。

例

入力:

5 2
8 2 10 1 5

処理の流れ: - ソート後: [10, 8, 5, 2, 1] - 二分探索で最大値の候補を試す。 - 例えば最大値を 5 にしたいなら、老朽度が 10, 8 の2教室にエアコンを置けばOK → 必要台数は2 → \(M=2\) なのでOK。

計算量

• 時間計算量: \(O(N \log N + N \log(\max(D)))\)
  • ソートに \(O(N \log N)\)、二分探索の各ステップで最大 \(N\) 個の要素を走査し、\(\log(\max(D))\) 回のステップが必要。
• 空間計算量: \(O(1)\)（入力データを除く）

実装のポイント

• 二分探索を用いる際は、left, right, mid の更新を慎重に行う。
• 判定関数 is_achievable() 内では、ソート済みの配列を利用して、必要な台数を高速に求めること。
• 入力を高速に読み込むために sys.stdin.read を使用している。

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    D = list(map(int, data[2:]))

    # 老朽度を降順にソートする
    D.sort(reverse=True)

    # 最大値を最小化する → 二分探索
    def is_achievable(max_val):
        # 老朽度がmax_valを超える教室には新しいエアコンが必要
        needed = 0
        for d in D:
            if d > max_val:
                needed += 1
            else:
                break
        return needed <= M

    # 二分探索の範囲
    left = 0
    right = max(D)
    answer = right

    while left <= right:
        mid = (left + right) // 2
        if is_achievable(mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    print(answer)

if __name__ == "__main__":
    main()

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