2017-05-02 AOJ 2527 MLE 問題 MLE | Aizu Online Judge 解法 そのままソートすると時間計算量O(NlogN)でTLE、空間計算量O(N)でMLEする。 そこで、乱数列の各要素の上位16bitをキーにしたバケットソートみたいなことをする。 k 番目の値を調べる部分では、値が小さいキーから順に辿っていく。 バケットソートの結果だけではちょうど K 番目の値が見つからないので、その後境界になっているバケットの中身だけをvectorに入れて普通にソートする。 x0=0のときがコーナーケースで、生成される乱数列の値は全て0となるため0を出力するようにしておく。詳細はソースコード参照