Kazun の競プロ記録

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

AtCoder Beginner Contest 273 C問題 (K+1)-th Largest Number

AtCoder ABC273 ABC C問題 300 pts

問題

提出解答

問題の概要

整数列 $A=(A_1, \dots, A_N)$ がある. $K=0,1,2, \dots, N-1$ に対して以下の問題を解け.

$1$ 以上 $N$ 以下の整数 $i$ のうち, $A$ に含まれる $A_i$ より大きい整数がちょうど $K$ 種類となるのは何個か?

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq 10^9$

解法

数列 $A$ から重複を除き, 降順にならべ, 初項を第 $0$ 項とした数列を $B$ とする. このとき, $1$ 以上 $N$ 以下の整数 $i$ に対して, $A_i=B_K$ となる非負整数 $k$ は唯一存在するが, 実はこのとき, $A_i$ より大きい整数はちょうど $K$ 種類になる.

このことから, $K=0,1, \dots, N-1$ に対して, 以下のことがわかる. ただし, $B$ の長さを $M$ と書くことにする.

$K \lt M$ ならば, 答えが $K$ になる $1$ 以上 $N$ 以下の整数 $i$ の個数は $B_K=A_i$ となる整数の個数と一致する.
$M \leq K$ ならば, 答えは $K$ になる $1$ 以上 $N$ 以下の整数 $i$ の個数は存在しない.

上のことから書く整数が何個出てくるかを記録し, $A$ にある整数の降順にその整数が $A$ に何個あるかを出力すれば良い.

計算量は $O(N)$ 時間である. なお, $(N-M)$ の $0$ も出力しなければならないことを忘れないこと.