CodeForces #256_Div2 : D. Multiplication Table

n * mの二次元テーブルが与えられる。
i行j列目の値はi * jと定義される。
このテーブルの内、k番目に大きい要素を答えよ。

例えば、n=2, m=3の場合テーブルは以下の図のようになり、
k=4 の時、その答えは3となる。
f:id:suigingin:20160207055557p:plain

n,mの最大値が $5·10^5$ と大きいため、
テーブルを愚直に構築し全探索を行うことはできない。

「ある数xがk番目に大きい」というのは以下のように言い換えられる

つまりk番目に大きい数は、ある数x以下の数がk個以上存在するような
最小のxを探せば良いことが分かる。
これはテーブル上にx以下の個数がいくつ存在するか調べる事ができれば、
二分探索で効率よく求めることができる。

では、テーブル上でどのようにx以下の個数を数える事ができるか。
これは行・列がそれぞれ単調増加している性質を利用してテーブルをジグザグ
移動しながら求めることができる。

例として4 * 5のテーブルで8以下の個数を数えたい場合、
以下のようにポインタを動かしその数は13個となる。

ジグザクする回数は高々(n+m)回のため、全体の計算量は $O((n+m)lognm)$ となる。

水銀メモ_________φ