yukicoder No.101 ぐるぐる！あみだくじ！

yukicoder No.100 直列あみだくじ - メモで以前述べたとおり置換は巡回置換の積でかける
この時これらの位数(=長さ)の最小公倍数が答えとなることはあきらか

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int lcm(int*a){
//配列に保存された値のLCMを求める
	if(a[1]==0)return a[0];
	a[1]*=a[0]/gcd(a[0],a[1]);
	return lcm(a+1);
}

int main(){
	int n,k,i,j,temp,times,num[110]={},x[1000],y[1000];
	scanf("%d%d",&n,&k);
	for(i=0;i<k;i++)scanf("%d%d",x+i,y+i);
	for(i=1;i<=n;i++){
	//各iが長さいくつの循環に属しているか求めたい
		temp=i;
		times=0;
		do{
			for(j=0;j<k;j++){
			//実際にあみだくじを実行
				if(x[j]==temp)temp=y[j];
				else if(y[j]==temp)temp=x[j];
			}
	
			times++;
		}while(temp!=i);
		//元に戻ってくるまでぐるぐる
		num[i]=times;
	}
	printf("%d",lcm(num+1));
	return 0;
}

実際にあみだくじをぐるぐるしなくても、読み込みながらあみだくじを実行していき「１回あみだくじを実行した結果」保存しておけば配列が節約できる

a[1010],x,y,c,i;
g(a,b){return b?g(b,a%b):a;}
main(s){
	scanf("%*d%*d");
	for(;~scanf("%d%d",&x,&y);a[y]=a[x]?a[x]:x,a[x]=i)i=a[y]?a[y]:y;
	//読み込みながらあみだくじの実行結果を保存していく
	//一度も他と入れ替わらなければ0が入っている
	for(i=101;y=--i;s*=c/g(s,c))for(c=1;(y=a[y])&&y-i;c++);
	//元に戻ってくるまでの長さを調べて順次最小公倍数を求めていく
	c=!printf("%d",s);
}

圧縮

//まず読み込みのごまかして
for(;~scanf("%d%d",&x,&y);a[y]=a[x]?a[x]:x*c,a[x]=i*c,c=1)i=a[y]?a[y]:y;
//ループ圧縮1
for(;y=--i;s*=c/g(s,c))for(c=1;(y=a[y])&&y-i;c++);
for(;(y=a[y])&&y-i?++c:(s*=c/g(s,c),c=1,y=--i););
//ループ圧縮2
for(;~scanf("%d%d",&x,&y);a[y]=a[x]?a[x]:x*c,a[x]=i*c,c=1)i=a[y]?a[y]:y;for(;(y=a[y])&&y-i?++c:(s*=c/g(s,c),c=1,y=--i););
for(;~scanf("%d%d",&x,&y)?i=a[y]?a[y]:y,a[y]=a[x]?a[x]:x*c,a[x]=i*c,c=1:(y=a[y])&&y-i?++c:(s*=c/g(s,c),c=1,y=--i););
//全部cへの代入があるのでそれらをまとめて
for(;~scanf("%d%d",&x,&y)?i=a[y]?a[y]:y,a[y]=a[x]?a[x]:x*c,a[x]=i*c,c=1:(y=a[y])&&y-i?++c:(s*=c/g(s,c),c=1,y=--i););c=!printf("%d",s);
for(;c=~scanf("%d%d",&x,&y)?i=a[y]?a[y]:y,a[y]=a[x]?a[x]:x*c,a[x]=i*c,1:(y=a[y])&&y-i?c+1:(s*=c/g(s,c),(y=--i)||!printf("%d",s)););

まとめると

a[999],x,y,z,c,t,i=100;
g(a,b){return b?g(b,a%b):a;}
main(s){for(;c=~scanf("%d%d",&x,&y)?t=a[y]?a[y]:y,a[y]=a[x]?a[x]:x*c,a[x]=t*c,1:(z=a[z])&&z-i?c+1:(s*=c/g(s,c),(z=--i)||!printf("%d",s)););}

191B

まだ短くなりそう？