Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 260 B問題 Better Students Are Needed!

AtCoder ABC ABC260 B問題 200 pts

問題

提出解答

問題の概要

$N$ 人が数学と英語の試験を受けた. $i$ 番目の人の数学の結果は $A_i$ 点, 英語の結果は $B_i$ 点であった.

この $N$ 人から次のようにして $(X+Y+Z)$ 人の合格者を決定する.

数学の点数が高い方から $X$ 人を合格とする.
まだ合格が決まっていない人の中での英語の点数が高い方から $Y$ 人を合格とする.
まだ合格が決まっていない人の中での数学の点数と英語の点数の合計が高い方から $Z$ 人を合格とする.
まだ合格が決まっていない人は全員不合格とする.

なお, 同点については番号が小さい方が上位であるとする.

このとき, 合格した $(X+Y+Z)$ 人の番号を列挙せよ.

制約

$1 \leq N \leq 1000$
$0 \leq X,Y,Z \leq N$
$1 \leq X+Y+Z \leq N$
$0 \leq A_i, B_i \leq 100$

解法

この問題はソートにおいて, 適切な観点によって, ソートできるか? ということを問われている.

これはつまり, 第1段階では

$\left [(-A_1,1), \dots, (-A_N,N) \right]$ を辞書式の昇順の観点で並び替える.

その後, 先頭 $X$ 人を合格させる. これを第2段階, 第3段階も同様に行っていけば良い. ただし, 合格させた人をそれ以降の段階で除外することを忘れないこと.