Codeforces #705 Div2 : E. Enormous XOR

後半割と苦労したな。
https://codeforces.com/contest/1493/problem/E

問題

2進数表記でN桁の整数L,Rが与えられる。
f(x,y)をx～yのxorを取ったものとする。
L≦x＜y≦Rの範囲でf(x,y)の最大値を求めよ。

解法

4n,4n+1,4n+2,4n+3のxorを取ると0となる。

そこで、
x=4k,4k+1,4k+2,4k+3
y=4m,4m+1,4m+2,4m+3
と両者下2bitを総当たりしよう。
あとはそれぞれのケースにおいて、4kおよび4mがf(x,y)に計上されるかされないかが定まるので、それぞれ最適なk,mを探索すればよい。

int N;
string L,R,X;

string inc(string S) {
	int i;
	for(i=S.size()-1;i>=0;i--) {
		if(S[i]=='1') {
			S[i]='0';
		}
		else {
			S[i]++;
			return S;
		}
	}
	S="2";
	return S;
}
string dec(string S) {
	int i;
	for(i=S.size()-1;i>=0;i--) {
		if(S[i]=='0') {
			S[i]='1';
		}
		else {
			S[i]--;
			return S;
		}
	}
	S="0";
	S[0]--;
	return S;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	cin>>L>>R;
	
	N+=2;
	L="00"+L;
	R="00"+R;
	X=R;
	
	int cx=(L[N-2]-'0')*2+L[N-1]-'0';
	int cy=(R[N-2]-'0')*2+R[N-1]-'0';
	FOR(x,4) FOR(y,4) {
		string L2=L.substr(0,N-2);
		string R2=R.substr(0,N-2);
		if(x<cx) L2=inc(L2);
		if(y>cy) R2=dec(R2);
		if(L2>R2) continue;
		// same
		if(y>=x) {
			r=0;
			int par=0;
			for(i=x;i<=y;i++) r^=i,par^=1;
			string T;
			if(par) T=R2;
			else T=string(N-2,'0');
			T.push_back('0'+r/2);
			T.push_back('0'+r%2);
			X=max(X,T);
		}
		
		if(L2<R2) {
			r=0;
			int p1=0,p2=0;
			for(i=x;i<=3;i++) r^=i,p1^=1;
			for(i=0;i<=y;i++) r^=i,p2^=1;
			string T;
			
			if(p1==0&&p2==0) {
				T=string(N-2,'0');
			}
			else if(p1==1&&p2==0) {
				T=dec(R2);
			}
			else if(p1==0&&p2==1) {
				T=R2;
			}
			else {
				int ok=0;
				FOR(i,N-2) {
					if(R2[i]=='1'&&L2[i]=='0') ok=1;
					T.push_back('0'+ok);
				}
			}
			
			T.push_back('0'+r/2);
			T.push_back('0'+r%2);
			X=max(X,T);
		}
		
	}
	cout<<X.substr(2)<<endl;
}

まとめ

コーナーケースとか割としんどい。