Codeforces #177 Div1. C. Polo the Penguin and XOR operation

本番でC解けたのは今回が初だった。
http://codeforces.com/contest/288/problem/C

問題

整数Nが与えられたとき、0～Nの(N+1)個の整数を１個ずつ含む整数配列P[i]のうち(0^P[0])+(1^P[1])+...+(N^P[N])が最大となるP[i]と最大値を答えよ。

解法

xorを取った値が最大値となるようにしたいので、当然xorを取ると111111bの様に1が並ぶようにしたい。
N以下の最大の2の累乗値をM=2^Lとする。
M-(N-M),M-(N-M)+1,M-(N-M)+2,,,M-1,M,M+1,...,Nという数列に対し
N,N-1,.....,M,M-1,M-2,.....,M-(N-M)とのxorを取ると各要素が2M-1となり最大値となる。

よってP[M-(N-M)]～P[N]が確定する。
あとは同様にP[0]～P[M-(N-M)-1]を計算していけばよい。

int N;
int A[1000003];

void dodo(int C) {
	int MB=1;
	int i;
	if(C<=0) return;
	while(MB*2<=C) MB*=2;
	for(i=0;i<=C-MB;i++) {
		A[MB+i]=MB*2-1-(MB+i);
		A[MB-1-i]=MB*2-1-(MB-1-i);
	}
	dodo(MB-(2+C-MB));
	
}

void solve() {
	int f,r,i,j,k,l,x,y;
	ll t=0;
	
	N=GETi();
	ZERO(A);
	dodo(N);
	
	FOR(i,N+1) t+=i^A[i];
	cout << t << endl;
	FOR(i,N+1) {
		if(i!=0) _P(" ");
		_P("%d",A[i]);
	}
	_P("\n");
	
	return;
}

まとめ

さほど長くないコードであっさり解ける面白い問題。
幸い本番にもすんなり解法を思いつけた。
まぁ他にも解けた人が多いからイマイチな順位なんだけどね。