yukicoder : No.74 貯金箱の退屈

これ☆２個なの…？
http://yukicoder.me/problems/127

問題

N個のコインが円形に順に並んでいる。
各コインの金額はD[i]円である。

あるコインi番を選択すると、時計回りおよび反時計まわりにD[i]個先の硬貨を表裏ひっくり返すことができる。
（ただし、時計回りも反時計回りも同じ硬貨を指す場合、１回だけひっくり返す）

各コインの初期の向き（表・裏）が与えられるとき、全コインを表向きに出来るか答えよ。

解法

２つの解法がある。

1つは、N変数のバイナリ値の方程式を立て、ガウスの掃出し法などで解く方法である。
自分はこちらは思いつかなかった。

もう1つは自分が取った方法。
N個のコインそれぞれを選択した場合、同時にひっくり返る２枚の組をUnion-findで連結していく。
互いに連結するコイン群は、２枚ずつひっくり返すことができる。
よって、連結されたコイン群のうち、裏向きのコインが奇数枚の場合、それらをすべて表にすることができない。
逆に偶数ならすべて表にすることができる。
例外として、連結成分中に１枚だけひっくり返せるコインがある場合、コインを１枚ずつ裏返すことができるので、裏返ったコインが奇数枚でもすべてを表にすることができる。

後者の方が計算時間短いけど、Nが100位ならどちらも通る。

int N;
int D[101];
int mat[101][101];
int num[101];
int ok[101];

class UF {
	public:
	static const int ufmax=1052;
	int ufpar[ufmax],ufrank[ufmax],ufcnt[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; ufcnt[i]=1; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	int count(int x) {return ufcnt[find(x)];}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y, ufcnt[y]+=ufcnt[x];
		else {ufpar[y]=x; ufcnt[x]+=ufcnt[y]; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	UF uf;
	cin>>N;
	FOR(i,N) {
		cin>>D[i];
		x=(i+D[i])%N;
		y=(i-D[i]+N*1000)%N;
		mat[x][y]=mat[y][x]=1;
		uf.unite(x,y);
	}
	
	FOR(x,N) if(mat[x][x]) ok[uf[x]]=1;
	FOR(x,N) cin>>y, num[uf[x]]+=y==0;
	
	FOR(x,N) if(uf[x]==x && num[x]%2 && ok[x]==0) return _P("No\n");
	_P("Yes\n");
	
}

まとめ

Union-Find解を思いついたときは面白い問題と思ったけど、掃出し法だと解法の面白さはないな…。