Codeforces #172 Div1. B. Maximum Xor Secondary

Bは本番中にpretestが通ったもののtestに失敗した。
http://codeforces.com/contest/280/problem/B

問題

ある数列に対するラッキーナンバーとは、数列中の最大値と２番目の値のxorである。
ここで、distinctな数列が与えられたとき、そこから連続要素からなる部分数列を作ったときに得られるラッキーナンバーの最大値を求めよ。

解法

数列中のMSBの最大値をMとすると、数列中にMを含む数は1つだけあるのが良い。
よって、数列を先頭から見て行って、Mを含む数を見つけるたびに、その前後の数値のうちMを含まない要素までを対象の部分数列とし、xorを計算して最大値候補とすればよい。

なお、初期状態で全要素のMSBが一致する場合は、そのMSBをすべて消しておく。

int N;
int S[100001];
int HB[100001];


void solve() {
	int f,r,i,j,k,l,x,y;
	int b1,b2,ma=0;
	
	N=GETi();
	FOR(i,N) S[i]=GETi();
ret:
	b1=99;
	b2=0;
	FOR(i,N) {
		if(S[i]==0) {
			b1=-1;
			HB[i]=-1;
			continue;
		}
		HB[i]=0;
		while((1<<(HB[i]+1))<=S[i]) HB[i]++;
		b1=min(b1,HB[i]);
		b2=max(b2,HB[i]);
	}
	
	if(b1==b2) {
		FOR(i,N) S[i] ^= 1<<b1;
		goto ret;
	}
	
	FOR(i,N) if(HB[i]==b2) {
		x=-1;
		for(j=i+1;j<N;j++) {
			if(HB[j]==b2) break;
			if(S[j]>x) {
				x=S[j];
				ma=max(ma,S[i]^S[j]);
			}
		}
		x=-1;
		for(j=i-1;j>=0;j--) {
			if(HB[j]==b2) break;
			if(S[j]>x) {
				x=S[j];
				ma=max(ma,S[i]^S[j]);
			}
		}
	}
	
	_P("%d\n",ma);
	
	return;
}

まとめ

一見O(N^2)かかりそうで、O(N)で処理できる問題。