Codeforces #173 Div2. E. Sausage Maximization

さて最終問題。
http://codeforces.com/contest/282/problem/E

問題

N個の要素からなる整数値の数列Aが与えられる。
このうち先頭からいくつかの要素と、末尾から(重複しないように)いくつかの要素を取ったとき、両者を合わせた要素のxorの最大値を答える。

解法

この問題は自力では回答が思いつかかったので、他の参加者のコードを見て、先頭と末尾の片方を木構造にすればよい、というアプローチだけ見て実装。

まず、先頭から順々に要素のxorを取っていった値P(A[0]、A[0]^A[1]、A[0]^A[1]^A[2]、、、)の値を木構造に配置していく。
この木構造では、数値を2進数表現した場合に、上位bitから順に２分木となるようにする。

次に、末尾から同様にxorを取っていき、その各値Q(A[N-1]、A[N-1]^A[N-2]、A[N-1]^A[N-2]^A[N-3]、、、)に対し、木構造を見てxorの値が最大となるような値を選ぶ。
この選び方は、木を上位から見て言って、Qと合わせて各bitのxorが1にできるようなPを優先的に取得し、無理な場合はxorが0になるPを選んでいく。

以下の処理では、各要素の最大値V=10^12に対しlogVと同程度の42の深さの２分木を作っている。
そのためこのコードはO(N logV)程度の時間がかかり、要素数が多いと若干TLEする。
そこで最大値更新の見込みがない場合は打ち切ることで高速化している。

２分木を深さ42も律儀に作らなければ、打ち切らなくても良さそうだ。

int N;
ll A[100002];
ll ma;
const int depth=42;
set<ll> S;
struct tree {
	tree *b0,*b1;
	int mi;
	ll val;
};
tree root;

void add(int ind,ll val, int bit,tree* ct) {
	if(bit<0) {
		ct->mi=ind;
		return;
	}
	
	if(val & (1LL<<bit)) {
		if(ct->b1==NULL) {
			ct->b1=new tree;
			ct->b1->b0=ct->b1->b1=NULL;
		}
		add(ind,val,bit-1,ct->b1);
	}
	else {
		if(ct->b0==NULL) {
			ct->b0=new tree;
			ct->b0->b0=ct->b0->b1=NULL;
			
		}
		add(ind,val,bit-1,ct->b0);
	}
}


ll query(int ind,ll val,int bit,tree* ct,ll ca) {
	if(bit==-1) return (ct->mi<=ind)?0:-1;
	ll tmp;
	ll tv=val & (~((1LL<<(bit+1))-1));
	
	if(val & (1LL<<bit)) {
		if(ct->b0) {
			tmp=query(ind,val,bit-1,ct->b0,ca | (1LL<<bit));
			if(tmp>=0) return tmp ^(1LL<<bit);
		}
		if((ca|(1LL<<bit))<ma) return -1;
		if(ct->b1) {
			tmp=query(ind,val,bit-1,ct->b1,ca);
			if(tmp>=0) return tmp ;
		}
	}
	else {
		if(ct->b1) {
			tmp=query(ind,val,bit-1,ct->b1,ca | (1LL<<bit));
			if(tmp>=0) return tmp ^(1LL<<bit);
		}
		if((ca|(1LL<<bit))<ma) return -1;
		if(ct->b0) {
			tmp=query(ind,val,bit-1,ct->b0,ca);
			if(tmp>=0) return tmp;
		}
	}
	
	return -1;
}

void solve() {
	int i,j,k,x,y;
	ll T;
	N=GETi();
	FOR(i,N) cin >> A[i];
	
	
	root.b0=root.b1=NULL;
	root.mi=-1;
	root.val=-1;
	add(0,0,depth,&root);
	T=0;
	FOR(i,N) {
		T^=A[i];
		if(S.find(T)==S.end()) add(i+1,T,depth,&root);
	}
	
	T=0;
	ma=0;
	ma=query(N,0,depth,&root,0);
	
	for(i=N;i>=1;i--){
		T^=A[i-1];
		ma=max(ma,query(i,T,depth,&root,0));
	}
	
	cout << ma << endl;
	
	return;
}

まとめ

２進数に応じて２分木を作るというアイデアは初めてだ。
でもこれ、xorの値を最大化する使う問題では利用できるシーンが多そうだ。