kmjp's blog

競技プログラミング参加記です

Codeforces #393 Div1 A. Pavel and barbecue

時間が時間なので不参加でした。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;
	
}

まとめ

出題意図がよくわからない問題だった。