全ての要素が異なるならば つの要素を固定させ、その他の全ての要素との大小比較によって で実装できますが、これでは制限時間に間に合いません。 また今回は全ての要素が異なるとは限らないので、このままではうまく実装ができません。 しかし要素が異なる場合のことについて戻ってみると、実は よりも効率的な時間で実装が可能です。
C++
などでは pair
配列が備われており、この配列を使ってソートすると実装が効率的になります。
その配列をここでは と表します。
まず 回目の数列の要素の入力段階では として別の配列 の 番目の要素 にまるごと格納します(すなわち となります)。
入力が終わった後、 を降順にソートします。このとき をソートした後の配列 として、 番目の最初の要素 ( の の部分)
は 番目に大きくなっていることがソートの性質から見てとれます。
ここで順位を決定する数値を とし、最初 です。これはどこかの要素が 番目に大きいことを表します。
そうして とする( は が降順にソートした数列内で 番目に大きい値のindexであり、ここでは 1-indexed とする)ことで、元の数列の 番目の要素 が 番目に大きいことがわかります。
そうして を ずつ増やしていけば、 番目に大きくなることが分かります。
しかしこのままでは を順々に ずつ増やすので同じ値があったとしても順位が重複することはないため、同じ要素が存在していた際に対応できません。
観察してみると、重複する際は事前に分かった順位 を活用すると順位を正しく修正できると思われます。今回の の範囲は までなので、これは map
などのデータ構造を用いて保存すると良いです。
また探索した際に同じ値が見つかった場合、その値のときの順位 は 以上なので事前に判定しておいてそのまま を格納すればよいです。
よってこの問題は で解くことができました。ちなみに二分探索を用いての実装も可能ですが、ここでは省略します。