まぁこれは一応解けた。
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で済んでよかった。