時間が時間なので不参加でした。Dを初見TLEしたのでどのみちTシャツはもらえなかったね。
http://codeforces.com/contest/759/problem/A
問題
コンロに1~NのN箇所串を刺す場所がある。
このコンロで肉をやこう。
1~NのPermutationで構成される数列A[i]と、01の2値をとるN要素の数列B[i]が与えられる。
今串が位置iにあるとき、その串は次に位置A[i]に動かし、かつB[i]=1ならその際肉を裏返す。
上記手順を繰り返すとき、全位置で表裏両方で焼くタイミングがあるようにしたい。
A,Bを最小何個変更する必要があるか。
解法
まずA[i]について、i-A[i]を無向辺でつなぐグラフを考えると、いくつかの閉路になる。
条件を満たすには、全体が1つの閉路でなければならない。
閉路が2個以上ある場合、各閉路について1箇所ずつA[i]を変更することで全体を1つの閉路にできる。
また、こうしてできた閉路において、B[i]中1が偶数個あると、N回状態遷移したのちに串の表裏が変わらないので、すべての状態を経由できない。
その場合、B[i]を1つ変更してB[i]中の1の数を奇数にしよう。
int N, A[202020], B[202020]; 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], A[i]--, uf(i,A[i]); x=1; FOR(i,N) cin>>B[i], x^=B[i]; int cnt=0; FOR(i,N) if(uf[i]==i) cnt++; if(cnt!=1) x += cnt; cout<<x<<endl; }
まとめ
出題意図がよくわからない問題だった。