No.507

K君以外の得点は降順にソートしておく.

K君があるの人とペアになったとき, $M$ 位以上になるためには, K君ペアの得点より高い得点の組が $M$ 組以上いないことが条件になる.

ここで, $M$ 組のペアの得点の最低点をなるべく高くすることを考える. まず, $M$ 組のペアは得点上位 $2M$ 人から選ぶのが最適である. この $2M$ 人の得点を $b_1, b_2, \dots, b_{2M}$ とする.

この得点群からペアを作ったときの最低点の最大値を $S(b_1, b_2, \dots, b_{2M})$ とする.

そして1番目の人がどの人と組むのが最適かを考える. 1番目の人は最後の人とペアを組むのが最適に見える. 実際, 最後の人とペアを組んだときと最後から2番目の人とペアを組んだときを考えてみると,

$$\min(b_1+b_{2M}, S(b_2, b_3, \dots, b_{2M-2}, b_{2M-1})) \\ \min(b_1+b_{2M-1}, S(b_2, b_3, \dots, b_{2M-2}, b_{2M}))$$

となる.

$b_1+b_{2M} \geq S(b_2, b_3, \dots, b_{2M-2}, b_{2M-1})$ のときは, $S(b_2, b_3, \dots, b_{2M-2}, b_{2M-1}) \geq S(b_2, b_3, \dots, b_{2M-2}, b_{2M})$ であるので, 最後から2番目の人とペアを組むと最低点が下がってしまう.

$b_1+b_{2M} \lt S(b_2, b_3, \dots, b_{2M-2}, b_{2M-1})$ のときは, $S(b_2, b_3, \dots, b_{2M-2}, b_{2M}) \leq b_1+b_{2M}$ となる. これは, $b_{2M}$ と組む相手は $b_1$ より小さいことが確定するからである. よってこの場合も最後から2番目の人とペアを組むと最低点が下がってしまう.

したがって, 最適に組んだときの最低点は,

$$\min(b_1+b_{2M}, b_2+b{2M-1}, b_3+b_{2M-2}, \dots)$$

となる. これがK君ペアを上回っていれば, K君は $M$ 位以内に入れないことになる.

あとはK君が誰とペアを組めばいいかを二分探索する.