Kodamanと愉快な仲間たち : P - Xor max

これは定番かな…。
https://www.hackerrank.com/contests/kodamanwithothers/challenges/xor-max

問題

整数列A[i]が与えられる。
非負整数xに対し、f(x) = max(A[i] xor x)とする。f(x)の最小値を求めよ。

解法

Aを2進数表記してTrieに入れ、各桁において寄り下の桁の値が小さい方が1になるようにしていく。

以下のコードは明にTrieを作ってないが、数列の区間を桁毎に細分化していて実質同じような処理をしている。

int N;
int A[101010];

int hoge(int L,int R,int D) {
	if(L>=R) return 1<<30;
	if(D<0) return 0;
	
	int M;
	for(M=L;M<R;M++) if(A[M]&(1<<D)) break;
	
	int A=hoge(L,M,D-1);
	int B=hoge(M,R,D-1);
	if(A==1<<30) return B;
	if(B==1<<30) return A;
	
	return (min(A,B)^(1<<D));
	
	
}

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

まとめ

さすがに類題が多そう。