kmjp's blog

競技プログラミング参加記です

AtCoder ARC #037 : C - 億マス計算

取りかかりにちょっと迷ったので、出遅れてしまった。
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でガチャガチャやるのかな?とか余計なことを考えてタイムロス。