第5回 ドワンゴからの挑戦状 本戦 : B - XOR Spread

お疲れ様でした。
https://atcoder.jp/contests/dwacon5th-final-open/tasks/dwacon5th_final_b

問題

整数列A[1...N]が与えられる。
両端以外の要素iを選び両隣要素をA[i-1] := A[i-1]^A[i]、A[i+1] := A[i+1]^A[i]で更新する、ということを任意に行えるとする。
その結果得られる整数列のうち、辞書順最小のものを求めよ。

解法

xorベースの累積和を考える。すなわちB[0]=0、B[i]=xor(A[1...i])とする。
そうすると、Aに対する処理というのはBにおける隣接２要素のswapとなる。
よって、結局問題の処理はBの要素を任意に入れ替えられることを意味する。

A[i]=B[i-1] xor B[i]なので、A[1]およびB[1]から順にA[i],B[i]を決めていこう。
A[i-1]およびB[i-1]が定まっているとき、未使用のBの要素のうち、B[i-1] xor B[i]が最小となるような物を選んでいけばよい。
これにはBの構成要素を固定長2進数表記してTrie木を作ればよい。

struct BinarySumTrie {
	BinarySumTrie *nex[2];
	ll v;
	BinarySumTrie() {
		nex[0]=nex[1]=NULL;v=0;
	}
	void add(ll s,ll val,int pos=29) {
		v += val;
		if(pos>=0) {
			int c=(s>>pos)&1;
			if(!nex[c]) nex[c]=new BinarySumTrie();
			nex[c]->add(s,val,pos-1);
		}
	}
	int pick(ll val,int pos=29) { // sum [0,s-1]
		v--;
		if(pos<0) return 0;
		
		int tar=0;
		if(val&(1LL<<pos)) {
			if(nex[1]&&nex[1]->v) tar=1;
			else tar=0;
		}
		else {
			if(nex[0]&&nex[0]->v) tar=0;
			else tar=1;
		}
		return (tar<<pos)+nex[tar]->pick(val,pos-1);
	}
};

BinarySumTrie root;

int N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int cur=0;
	int last;
	FOR(i,N) {
		cin>>x;
		cur^=x;
		if(i==N-1) last=cur;
		else root.add(cur,1);
	}
	cur=0;
	FOR(i,N) {
		if(i<N-1) x=root.pick(cur);
		else x=last;
		cout<<(cur^x)<<" ";
		cur=x;
	}
	cout<<endl;
}

まとめ

隣接要素と何かする形の問題は、数列の差分とか累積和とか取るとよさそうね。