AtCoder AGC #016 : D - XOR Replace

まぁこれは一応解けた。
http://agc016.contest.atcoder.jp/tasks/agc016_d

問題

N要素の数列A、Bが与えられる。
Aに以下の操作を繰り返し、AをBにできるか判定せよ。
できるなら、最小の操作回数を求めよ。

• Aの各要素のxorを取った値をxとする。Aの1つの要素A[i]をxにする。

解法

A[0]^A[1]^A[2]...^A[N-1]=xとする。
A[0]^A[1]^A[2]...^A[N-1]^x=0より、仮にA[i]をxにする処理を行うと、それらのxorはA[i]となる。

よって本質的にはこの操作は(N+1)要素(元のAのN要素と、初期状態における全要素のxor)におけるswapとみなすことができる。
そのため、A,Bをそれぞれ1要素増やし、A[N]=xor(A[0..(N-1)]、B[N]=xor(B[0..(N-1)])とすると、両者が並び替えることで一致するならば解が存在する。

これで一致可能は判定できた。あとは最小操作回数である。
任意のiを選び、A[i]とA[N]をswapすることを繰り返しAをBにすることを考える。
すでにA[i]=B[i]である要素は無視して考えよう。
今ここで、B[x[0]]=A[x[1]]、B[x[1]]=A[x[2]]、B[x[2]]=A[x[3]]、...B[x[n-1]]=A[x[0]]のようにAを回転させると一致するような添え字の順を考える。
x中にNが含まれていればこれらはn回のswapでAとBを一致させることが、含まれていなければ(n+1)回のswapで一致させることができる。
よってxは可能な限り長い列を取り、全体をA=Bにするために処理するxの数を減らした方が、swap回数を減らすことができる。

そのようなxの数を求めよう。
まずA,Bのうち、A[i]!=B[i]である、またはi=NであるようなA[i],B[i]を座標圧縮しよう。
あとはA[i]!=B[i]の時Union-findで値A[i]とB[i]を連結する。
連結成分内は、全体を1個のxで一致させることができるので、解は((A[i]!=B[i])となるiの数) + (連結成分-1)となる。

int N;
int A[101010];
int B[101010];
map<int,int> M[2];
map<int,int> T;
int is[101010];

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<500000> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	int cur[2]={};
	FOR(i,N) {
		cur[0] ^= A[i];
		cur[1] ^= B[i];
		M[0][A[i]]++;
		M[1][B[i]]++;
		T[A[i]]=T[B[i]]=0;
	}
	M[0][cur[0]]++;
	M[1][cur[1]]++;
	if(M[0]!=M[1]) return _P("-1\n");
	T[cur[0]]=T[cur[1]]=0;
	x=0;
	FORR(r,T) r.second=x++;
	
	is[T[cur[0]]]=is[T[cur[1]]]=1;
	uf(T[cur[0]],T[cur[1]]);
	int ns=0;
	FOR(i,N) if(A[i]!=B[i]) {
		ns++;
		is[T[A[i]]]=is[T[B[i]]]=1;
		uf(T[A[i]],T[B[i]]);
	}
	
	FOR(i,T.size()) if(is[i]&&uf[i]==i) ns++;
	ns--;
	cout<<ns<<endl;
}

まとめ

巡回に持ち込むところからちょっと悩んだけど、Union-Findで済んでよかった。