概要

\(N\) 個の教室の老朽度 \(D_i\) が与えられたとき、最大 \(M\) 台のエアコンを設置して（設置した教室の老朽度を \(0\) にして）、全教室の老朽度の最大値を最小化する問題です。

考察

この問題の目標は「全体の最大値をできるだけ小さくする」ことです。

ある教室に新しいエアコンを設置すると、その教室の老朽度は \(0\) になります。全体の老朽度の最大値を下げるためには、現在老朽度が高い（値が大きい）教室から優先的にエアコンを設置するのが最も効率的です。

例えば、老朽度が \([10, 50, 100]\) の 3 つの教室があり、エアコンが 1 台ある場合を考えてみましょう。 - 老朽度 \(10\) の教室に設置した場合：老朽度は \([0, 50, 100]\) となり、最大値は \(100\) です。 - 老朽度 \(100\) の教室に設置した場合：老朽度は \([10, 50, 0]\) となり、最大値は \(50\) です。

このように、値が大きいものから順に \(M\) 個選んで \(0\) に書き換えることで、残った値の中の最大値が、達成可能な最小の最大値となります。

アルゴリズム

1. 教室の老朽度のリスト \(D\) を昇順（小さい順）にソートします。
2. もしエアコンの台数 \(M\) が教室の数 \(N\) 以上であれば、すべての教室にエアコンを設置できるため、最大値は \(0\) になります。
3. エアコンの台数 \(M\) が \(N\) より少ない場合、老朽度が高い方から \(M\) 個の教室にエアコンを設置します。
   • ソート済みのリスト \(D\) において、後ろから \(M\) 個の要素が \(0\) になります。
   • 残った要素の中で最大のものは、ソート済みリストの \(N-M\) 番目（0-indexed ではインデックス \(N-M-1\)）の要素です。
4. その値を答えとして出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • データの読み込みに \(O(N)\)、リストのソートに \(O(N \log N)\) かかります。その後の値の参照は \(O(1)\) です。
• 空間計算量: \(O(N)\)
  • \(N\) 個の老朽度を保持するリストのためのメモリが必要です。

実装のポイント

• \(N\) や \(M\) の値が最大 \(2 \times 10^5\) と大きいため、Python では sys.stdin.read().split() などを用いて高速に入力を処理するのが望ましいです。

• ソート後のインデックス指定を間違えないように注意しましょう。例えば \(N=5, M=2\) のとき、ソート済みリスト \(D = [D_0, D_1, D_2, D_3, D_4]\) のうち大きい方から 2 つ（\(D_3, D_4\)）を \(0\) にするため、残る最大値は \(D_{5-2-1} = D_2\) となります。

  ソースコード

import sys

def solve():
    # 入力をすべて読み込み、スペースや改行で分割する
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # N: 教室の数, M: 新しいエアコンの台数
    n = int(input_data[0])
    m = int(input_data[1])
    
    # D: 各教室の老朽度
    d = list(map(int, input_data[2:]))
    
    # 老朽度を昇順（小さい順）にソートする
    d.sort()
    
    # 老朽度の最大値を最小化するためには、老朽度が高い教室から優先的に
    # 新しいエアコンを設置するのが最適である。
    # 最大M台のエアコンを設置できるため、老朽度が大きい方からM個を0に置き換える。
    
    if m >= n:
        # エアコンの台数が教室の数以上であれば、すべての教室の老朽度を0にできる
        print(0)
    else:
        # エアコンをM台設置したとき、残った教室の中で最大の老朽度は、
        # ソート後のリストにおいて後ろからM個を除いた中での最大値、
        # すなわちインデックス N-M-1 の要素となる。
        print(d[n - m - 1])

if __name__ == '__main__':
    solve()

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