AtCoder Beginner Contest 273 C問題 (K+1)-th Largest Number
問題
提出解答
問題の概要
整数列 がある.
に対して以下の問題を解け.
以上
以下の整数
のうち,
に含まれる
より大きい整数がちょうど
種類となるのは何個か?
制約
解法
数列 から重複を除き, 降順にならべ, 初項を第
項とした数列を
とする. このとき,
以上
以下の整数
に対して,
となる非負整数
は唯一存在するが, 実はこのとき,
より大きい整数はちょうど
種類になる.
このことから, に対して, 以下のことがわかる. ただし,
の長さを
と書くことにする.
ならば, 答えが
になる
以上
以下の整数
の個数は
となる整数の個数と一致する.
ならば, 答えは
になる
以上
以下の整数
の個数は存在しない.
上のことから書く整数が何個出てくるかを記録し, にある整数の降順にその整数が
に何個あるかを出力すれば良い.
計算量は 時間である. なお,
の
も出力しなければならないことを忘れないこと.