面白かったです。
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回未満のケースもあるので最小公倍数を求めないといけないのか。