概要

老朽度配列 \(D\) から最大 \(M\) 個の教室を選んで老朽度を \(0\) にできるとき、設置後の「老朽度の最大値」を最小にする値を求めます。

考察

新しいエアコンを入れるとその教室の老朽度は必ず \(0\) になるため、「どの教室を \(0\) にするか」だけが問題になります。

ここで重要な観察は次の通りです：

• 老朽度の最大値を下げたいなら、大きい老朽度を優先して \(0\) にするのが最適です。
  もし大きい値を残して小さい値を \(0\) にしても、最大値は大きい値のままで下がりません。

例えば \(D=[8,5,3,1],\ M=1\) のとき： - \(8\) を \(0\) にすると残りは \([5,3,1,0]\) で最大は \(5\) - \(1\) を \(0\) にすると残りは \([8,5,3,0]\) で最大は \(8\)（改善しない）

したがって、最大値を最小化するには「老朽度が大きい順に \(M\) 個を \(0\) にする」のが最善です。

素朴に「どの教室に置くか」を全探索すると、組合せは \({N \choose M}\) 通りで \(N \le 2\times 10^5\) では到底間に合いません（TLE）。

この観察により、実際には 並べ替え だけで答えが決まります。

アルゴリズム

1. 配列 \(D\) を降順（大きい順）にソートする。
2. もし \(M \ge N\) なら全教室を \(0\) にできるので答えは \(0\)。
3. そうでなければ、上位 \(M\) 個を \(0\) にした後に残る最大値は「元の \((M+1)\) 番目に大きい値」。
   0-indexed で降順配列を \(D\) とすると答えは \(D[M]\)。

（降順に並べたとき、添字 \(0 \sim M-1\) が設置対象、残る部分の先頭 \(D[M]\) が最大になります。）

計算量

• 時間計算量: \(O(N \log N)\)（ソート）
• 空間計算量: \(O(N)\)（配列の保持）

実装のポイント

• 降順ソート後に \(D[M]\) を出力する（0-indexedに注意）。

• \(M = N\) のときは \(D[M]\) にアクセスできないため、先に \(M \ge N\) を判定して \(0\) を出力する。

• 入力サイズが大きいので sys.stdin.buffer.read() を使うと安全に高速化できます。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M = data[0], data[1]
    D = data[2:]
    D.sort(reverse=True)
    if M >= N:
        print(0)
    else:
        print(D[M])

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。