取りかかりにちょっと迷ったので、出遅れてしまった。
http://arc037.contest.atcoder.jp/tasks/arc037_c
問題
2つのN要素の正整数列A[i]、B[j]が与えられる。A[i]*B[j]のうち、昇順K番目のものを答えよ。
解法
N*N個の積を全列挙すると9*10^8通りあるので、当然全列挙は間に合わない。
二分探索で「V以下の数値がK個ある」というようなVの下限を求めればよい。
先にB[j]を昇順ソートしておくと、各iに対してA[i]*B[j]≦Vとなるjの数がO(logN)で求められる。
よって全体でV以下の数値の個数はO(N*logN)で求められる。
計算量は全体でO(log(maxA*maxB)*N*logN)かな。
int N; ll K,A[40100],B[65537]; ll num(ll v) { ll tot=0; int x,i; FOR(x,N) { int y=0; for(i=15;i>=0;i--) { int y2=y+(1<<i); if(y2>N) continue; if(A[x]*B[y2-1]<=v) y=y2; } tot+=y; } return tot; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; FOR(i,N) cin>>A[i]; FOR(i,N) cin>>B[i]; sort(A,A+N); sort(B,B+N); ll V=(1LL<<61)-1; for(i=60;i>=0;i--) if(num(V-(1LL<<i))>=K) V-=1LL<<i; cout<<V<<endl; }
まとめ
priority_queueでガチャガチャやるのかな?とか余計なことを考えてタイムロス。