kmjp's blog

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

yukicoder : No.101 ぐるぐる!あみだくじ!

面白かったです。
http://yukicoder.me/problems/213

問題

縦本がN本あるあみだくじの形状が当たられる。
出発点と到着点が等しくなるためには、あみだくじを最小何個縦に連結すればよいか。

解法

各頂点について、何回あみだくじを辿れば元の場所に戻れるか求める。
あとはその数の最小公倍数を求めればよい。

各頂点は最大でもN回以内には元の場所に戻れるので、O(N^2)で計算できる。

int N,K;
int A[2][101],R[101],rev[101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) R[i]=i;
	while(K--) {
		cin>>x>>y;
		swap(R[x-1],R[y-1]);
	}
	
	ll ret=1;
	FOR(i,N) {
		for(x=i,y=0;y==0 || x!=i;y++) x=R[x];
		ret=ret*y/__gcd(ret,(ll)y);
	}
	cout<<ret<<endl;
	
}

まとめ

最初N回以内にもとに戻れるかと思ったけど、頂点によってはN回未満のケースもあるので最小公倍数を求めないといけないのか。