AtCoder ARC #152 : E - Xor Annihilation

解き切れて良かったね。
https://atcoder.jp/contests/arc152/tasks/arc152_e

問題

数直線の座標1～(2^N-1)の各点xに、重さW[x]のボールがある。
Wは1～(2^N-1)の順列となっている。

また、正負無限大の座標の位置に、(2^N-1)以下の任意の非負整数の重さZを持つボールを置く。

この状態で各ボールは以下のように動作する。

• 左右方向それぞれで、その向きにあるボールの重さのxorを取る。
• 両者に差があれば、重い方に等速で移動する。
• もしボールが2つ同じ座標に重なった場合、合体して重さは両者のxorとなる。

最終的にすべてのボールが停止するZは何通りか。

解法

上のbitから順に、Zが0/1の場合ボールが停止するかを見ていこう。
その時点でそのbitが立っているボールが1個でもある場合、Zのそのbitは0でなければならない。そうでない場合、0/1のどちらでも良い。
その後、そのbitがすべて消えるまでボールの移動をシミュレートしていく。

int N;
int W[1<<18];
ll S[1<<18];

int ok[18];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	x=0;
	vector<ll> A;
	FOR(i,(1<<N)-1) {
		cin>>x;
		A.push_back(x);
	}
	FOR(i,N) ok[i]=2;
	
	
	for(int cur=N-1;cur>=0;cur--) {
		FORR(a,A) {
			if(a&(1<<cur)) ok[cur]=1;
		}
		
		vector<ll> B;
		int state=0;
		FORR(a,A) {
			if(a&(1<<cur)) {
				if(state==0) {
					B.push_back(a);
					state=1;
				}
				else {
					B.back()^=a;
					state=0;
				}
			}
			else if(state) {
				B.back()^=a;
			}
			else {
				B.push_back(a);
			}
		}
		A=B;
	}
	
	int ret=1;
	FOR(i,N) ret*=ok[i];
	cout<<ret<<endl;
	
	
}

まとめ

annihilateって単語、ちょうど英単語帳で覚えた直後に遊○王のアニメでこの単語出てきて脳内の記憶が強化されたことがある。