全ての要素が異なるならば 11 つの要素を固定させ、その他の全ての要素との大小比較によって O(N2)O(N^2) で実装できますが、これでは制限時間に間に合いません。 また今回は全ての要素が異なるとは限らないので、このままではうまく実装ができません。 しかし要素が異なる場合のことについて戻ってみると、実は O(N2)O(N^2) よりも効率的な時間で実装が可能です。

C++ などでは pair 配列が備われており、この配列を使ってソートすると実装が効率的になります。 その配列をここでは PP と表します。

まず i (1iN)i\ (1\le i\le N) 回目の数列の要素の入力段階では P[Ai][i]P[A_i][i] として別の配列 VVii 番目の要素 ViV_i にまるごと格納します(すなわち Vi=P[Ai][i]V_i=P[A_i][i] となります)。 入力が終わった後、VV を降順にソートします。このとき VV をソートした後の配列 VV' として、j (1jN)j\ (1\le j\le N) 番目の最初の要素 (P[Ai][i]P[A_i][i]AiA_i の部分) は jj 番目に大きくなっていることがソートの性質から見てとれます。 ここで順位を決定する数値を rankrank とし、最初 rank=1rank=1 です。これはどこかの要素が rankrank 番目に大きいことを表します。 そうして Kij=rankK_{i_j}=rank とする( iji_jAiA_i が降順にソートした数列内で jj 番目に大きい値のindexであり、ここでは 1-indexed とする)ことで、元の数列の ii 番目の要素 AiA_irankrank 番目に大きいことがわかります。 そうして rankrank11 ずつ増やしていけば、rank=1,2,...Nrank=1,2,...N 番目に大きくなることが分かります。 しかしこのままでは rankrank を順々に 11 ずつ増やすので同じ値があったとしても順位が重複することはないため、同じ要素が存在していた際に対応できません。 観察してみると、重複する際は事前に分かった順位 rankrank を活用すると順位を正しく修正できると思われます。今回の AiA_i の範囲は 10910^9 までなので、これは map などのデータ構造を用いて保存すると良いです。 また探索した際に同じ値が見つかった場合、その値のときの順位 rankrank11 以上なので事前に判定しておいてそのまま rankrank を格納すればよいです。

よってこの問題は O(NlogN)O(N\log_{}{N}) で解くことができました。ちなみに二分探索を用いての実装も可能ですが、ここでは省略します。

解答例 -> https://matcharate12pro.hatenablog.com/entry/2022/08/13/151427?_ga=2.37337184.1315491606.1660370318-763410119.1618053777