yukicoder No.130 XOR Minimax

数の集合Xが与えられた時、この問題の答えを返す関数を形式的にfとしておく
f(X)は次のように再帰的に求めることができる
方針としては「xを上の位から決めていきたい」

Xが一元集合ならf(X)=0。そうでないとする
maxX＜2^(k+1)なるkをとる
A={x∈X|x＜2^k}
B={x∈X|x≧2^k}とし
B-2^k={b-2^k|b∈B}とする
・xのkbit目(0-based)を0とすると
Aの元a[i]に対して(a[i] bitxor x)＜2^kであり
Bの元a[i]に対して2^k≦(a[i] bitxor x)＜2^(k+1)となる
よって（kbit目以上の桁はもう決まったので）求める最大値は
Bが空でないならf(B-2^k)+2^k
Bが空ならf(A)
・xのkbit目を1とすると
Aの元a[i]に対して2^k≦(a[i] bitxor x)＜2^(k+1)であり
Bの元a[i]に対して(a[i] bitxor x)＜2^kとなる
よって求める最大値は
Aが空でないならf(A)+2^k
Aが空ならf(B-2^k)

よって２つをまとめて
Aが空ならf(B-2^k)
Bが空ならf(A)
どちらも空でないなら2^k+min(f(A),f(B-2^k))

このように再帰的したとき、kとして取れる値が真に小さくなっていくのでこれでwell-defined

a[100010];
c(int*a,int*b){return*a-*b;}

int x(int*a,int n,int i){
	//n要素からなる数の集合aに対して、上からibit目を決めたい
	int l,u,m;
	if(i==-1)return 0;
	if(~(*a^a[n-1])>>i&1)return x(a,n,i-1);
	//最小の数と最大の数のibit目が同じならAかBが空
	for(l=0,u=n;u-l>1;a[m=(l+u)/2]>>i&1?u=m:(l=m));
	//そうでないならAとBの集合に分けて
	l=x(a,u,i-1);m=x(a+u,n-u,i-1);
	//lにf(A)、mにf(B-2^i)をいれて
	return 1<<i|(l<m?l:m);
	//小さい方を返す
}

int main(){
	int n,i;
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",a+n);
	qsort(a,n,4,c);
	printf("%d",x(a,n,29));
	//a[i]<=1e9なので29bit目から決めれば良い
	return 0;
}

ちゃちゃっと縮める

y,a[1<<17];
c(int*a,int*b){y=*a-*b;}
x(s,n,i){
	int l=s,u=n,m;
	for(;u-l>1;a[m=l+u>>1]&i?u=m:(l=m));
	y=i?(a[s]^a[n-1])&i?i|((l=x(s,u-s,i/2))<(m=x(u,n-u,i/2))?l:m):x(s,n,i/2):0;
}
main(n){
	for(n=-2;~scanf("%d",++n+a););
	qsort(a,n,4,c);
	y=!printf("%d",x(0,n,1<<29));
}

xの引数を全部intにしたいので、最初と最後の添字を渡すことにする

y,a[1<<17];
c(int*a,int*b){y=*a-*b;}
x(s,n,i){
	int l=s,u=n,m;
	for(;u-l>1;a[m=l+u>>1]&i?u=m:(l=m));
	y=i?(a[s]^a[n-1])&i?i|((l=x(s,u,i/2))<(m=x(u,n,i/2))?l:m):x(s,n,i/2):0;
}
main(n){
	for(n=-2;~scanf("%d",++n+a););
	qsort(a,n,4,c);
	y=!printf("%d",x(0,n,1<<29));
}

よく睨んでいらない変数を消す

y,a[1<<17],m=-2;
c(int*a,int*b){y=*a-*b;}
x(s,n,i,l,u){
	for(l=s,u=n;u-l>1;a[m=l+u>>1]&i?u=m:(l=m));
	y=i?(a[s]^a[n-1])&i?i|((l=x(s,u,i/2))<(m=x(u,n,i/2))?l:m):x(s,n,i/2):0;
}
main(){
	for(;~scanf("%d",++m+a););
	qsort(a,m,4,c);
	y=!printf("%d",x(0,m,1<<29));
}

246B

メモ

yukicoderでゆるふわgolf

yukicoder No.130 XOR Minimax