Kazun の競プロ記録

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

AtCoder Beginner Contest 228 C 問題 Final Day

AtCoder ABC ABC228 C問題 300 pts

問題

提出解答

問題の概要

$N$ 人が $4$ 日間からなる試験を受けた. 各日の試験は $300$ 点満点である.

$3$ 日目終了時, $i$ 番目の生徒の $j$ 日目の得点は $P_{i,j}$ 点であった.

全ての $i=1,2, \dots, N$ について, 以下の質問を答えよ.

$4$ 日目終了後, $i$ 番目の生徒は $4$ 日間の試験の得点の総和で降順 $K$ 番以内になり得るか (同率は上の順位).

制約

$1 \leq K \leq N \leq 10^5$
$0 \leq P_{i,j} \leq 300$
入力は全て整数である.

解法

各 $i$ 番目の生徒において, 降順 $K$ 番以内になるために最も有利な $4$ 日目の結果は以下である.

$i$ 番目の生徒は満点 ( $300$ 点) である.
$i$ 番目の生徒以外は皆 $0$ 点である.

よって, $Q_i:=P_{i,1}+P_{i,2}+P_{i,3}$ とし, $Q_i$ の $K$ 番目に大きい値を $R$ としたとき, $Q_i+300 \geq R$ となるかどうかを判定すれば良い.

計算量は $R$ を求めるためのソートがボトルネックになり, $O(N \log N)$ である.