ARC037 C.億マス計算

その他

GCJ2015Round1A B問題に似ているかも？こちらもハマって時間を溶かした。
本番では数か所間違えててWA。

問題

N*Nマスの表があり、(i,j)の値はA[i]*B[j]である。
サイズNの配列A,Bが与えられるとき、表の中の数値を昇順で並べてK番目にくる数値を求める。

N<=30000
1<=K<=N^2
1<=A[i],B[i]<=10^9

解いた方法

二分探索で、「表の中でx以下の整数が何個あるか？を求めてそれがK以下である」を満たすような最大整数x(表に無くてもよい)を求める。


「表の中でx以下の整数が何個あるか？を求めてそれがK以下である」の条件を確かめるには、A[i]に対して、ソート済みBでA[i]*B[j]がx以下かつ最大となるなるB[j]を二分探索で求めればよいのでO(NlogN)。


上の最大整数xは表で作れる整数とは限らない。x以下の整数で、かつ、表で作れる最大整数yは、A[i]に対して二分探索でソート済みのB[j]でA[i]*B[j]<=xとなる最大のB[j]を求めればA[i]*B[j]の中で最大のもの、で求められる。O(NlogN)。

最初の二分探索がO(log 10^18)ぐらいで、条件判定がO(NlogN)、表で作れる整数を求めるのにO(NlogN)なので、全体でO(NlogN * log 10^18 + NlogN)なので、間に合う。

反省

愚直解と照らし合わせて、きちんとできているか確認する。
テストケースにあるやつでもKを変えてきちんと返せてるかどうか確認。
コーナーケース(二分探索で満たせるものが無い場合)の処理が抜けてしまっていた。