AtCoder Beginner Contest 228 C 問題 Final Day
問題
提出解答
問題の概要
人が
日間からなる試験を受けた. 各日の試験は
点満点である.
日目終了時,
番目の生徒の
日目の得点は
点であった.
全ての について, 以下の質問を答えよ.
日目終了後,
番目の生徒は
日間の試験の得点の総和で降順
番以内になり得るか (同率は上の順位).
制約
- 入力は全て整数である.
解法
各 番目の生徒において, 降順
番以内になるために最も有利な
日目の結果は以下である.
番目の生徒は満点 (
点) である.
番目の生徒以外は皆
点である.
よって, とし,
の
番目に大きい値を
としたとき,
となるかどうかを判定すれば良い.
計算量は を求めるためのソートがボトルネックになり,
である.