Codeforces ECR #032 : G. Xor-MST

これ系いい加減に対策しようかな…。
http://codeforces.com/contest/888/problem/G

問題

N個の頂点があり、それぞれ整数X[i]が振られている。
頂点u,v間を辺でつなぐコストを(X[u] xor X[v])とする。
最小全域木を構築するコストを求めよ。

解法

Xを昇順ソートしよう。
コストを上のビットから見ていき、例えば上からd bit目が初めて異なるような頂点群X,Yが存在したとする。
(Xはd bit目が0、Yはd bit目が1の整数がそれぞれ1個以上入っている)

XとYを連結させるため、両者から1個ずつ頂点を選びそのxorが最小となるものを選んでいけばよい。
こればX,Yのうち片方の構成要素を全探索しつつ、もう片方の要素からxorが最少となるものとBinary Trie探索の要領で選んでいく。

連結回数はO(log(max(X)))、Binary Trie探索の計算量はO(log(max(X)))なので、全体でもO(N*log^2(max(X)))で終わる。

以下はBinary Trieのライブラリがないため、ソート済み配列にlower_boundで二分探索を繰り返すことでごまかしている。

int N;
int A[202020];
ll ret;

void dfs(int L,int R,int level) {
	if(R-L<2 || level<0) return;
	int M,i;
	M=lower_bound(A+L,A+R,1<<level)-A;
	
	for(i=M;i<R;i++) A[i]^=1<<level;
	if(L<M &&M<R) {
		int mi=1<<30;
		for(i=L;i<M;i++) {
			int X=M,Y=R;
			int cur=0;
			for(int l=level-1;l>=0;l--) {
				int Z=lower_bound(A+X,A+Y,cur+(1<<l))-A;
				
				if(Z==X) {
					cur+=1<<l;
				}
				else if(Z==Y) {
				}
				else if(A[i]&(1<<l)) {
					X=Z;
					cur+=1<<l;
				}
				else {
					Y=Z;
				}
			}
			
			mi=min(mi,A[i]^A[X]);
		}
		ret+=(1LL<<level)+mi;
	}
	dfs(L,M,level-1);
	dfs(M,R,level-1);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	sort(A,A+N);
	
	dfs(0,N,29);
	
	cout<<ret<<endl;
	
}

まとめ

いい加減Trie作ろうかな…。