読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.100 直列あみだくじ

問題はこちら
No.100 直列あみだくじ - yukicoder

置換の知識を既知とする
置換σが与えられた時、置換τであってτ^2=σとなるようなものが存在するかを判定する問題
「任意の置換は、同じ文字を含まない巡回置換たちの積で表される」ということを思い出し、まず巡回置換について考える
ρを位数nの(つまり長さnの)巡回置換とし、ρ=(a1 a2 … an)とする
nが奇数のときρ^2=(a1 a3 … an a2 a4 … an-1)となる。(ρ^2は長さnの巡回置換)
nが偶数のときρ^2=(a1 a3 … an-1)(a2 a4 … an)となる(ρ^2は長さn/2の巡回置換2つの積)
よってτ^2=σとなるようなτが存在するためには、σを同じ文字を含まない巡回置換たちの積に分解した時、全ての偶数nに対して「位数nの巡回置換は偶数個」が成立していることが必要
逆にσがこの条件を満たす時、τ^2=σなるτが存在することを示す
まず巡回置換について考える。
ρ=(a1 a2 … an)を奇数位数n=2k+1の巡回置換とすると
τ=(a1 ak+1 a2 ak+2 a3 … ak-1 an ak)とすればτ^2=ρ
ρ=(a1 a2 … an)、ρ'=(b1 b2 … bn)を偶数位数nの巡回置換とすると
τ=(a1 b1 a2 b2 … an bn)と定めるとτ^2=ρρ'
こうして作ったτは元の置換と同じ文字しか含んでいないので、一般の置換σに対しては、σを巡回置換の積に分解し、その各々ρに対してτ^2=ρなる物を見つけ、それらの積を取ることで求めるものが得られる

ということで、各循環置換の長さを求める

int main(){
	int n,i,s,t,a[51],b[51]={};
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",a+i);
	for(i=1;i<=n;i++){
	//一度調べたところは0で潰す
		if(a[i]==0)continue;
		s=0;
		while(a[i]){
		//元に戻ってくるまで
			t=a[i];
			a[i]=0;
			//現在地を0につぶして
			i=t;
			//移動
			s++;
			//循環の長さをinc
		}
		b[s]++;
	}
	s=1;
	for(i=0;i<=n;i+=2){
	//奇数の長さはどうでもいいので偶数だけ見る
		if(b[i]%2!=0){s=0;break;}
	}
	puts(s?"YES":"NO");
	return 0;
}

偶奇だけわかればいいんだから、配列bで保存しないで、bitで保存する

s,a[51],y,i;main(c){
	for(;~scanf("%d",a+i);i++);
	//nもまとめて読み込んだおかげでindexずれ解消
	for(;--i;){
		y=i;
		c=0;
		do{
			y=a[y];
			c++;
		}while(y<i);
		//スタート地点以上の値が出てきたら、スタートに戻ってきたor前に見た
		if(y==i&&c%2==0)s^=1<<c/2;
		//今まで見たこと無い循環で長さが偶数ならbitで保存
	}
	s=!puts(s?"No":"Yes");
}

これを短くして

s,a[51],y,i;main(c){
	for(;~scanf("%d",a+i);i++);
	for(;y=--i;s^=y-i|c%2?0:1<<c-1)for(c=1;(y=a[y])&&y<i;c++);
	s=!puts(s?"No":"Yes");
}

for文圧縮

for(;y=--i;s^=y-i|c%2?0:1<<c-1)for(c=1;(y=a[y])&&y<i;c++);
//↑これを ↓形式的に変形
for(;(y=a[y])&&y<i?c++:(s^=!(y-i|c%2)<<c/2,c=1,y=--i););
//yの初期値は0なので、このままだと無限ループ
//yにはn+1以上の値を渡しておきたい……?→iが読み込みループ終わった時点でn+1になってるじゃん

for(;~scanf("%d",a+i);i++);for(;(y=a[y])&&y<i?c++:(s^=!(y-i|c%2)<<c/2,c=1,y=--i););
//なので↑これを ↓こう
for(;~scanf("%d",a+i)?y=++i:(y=a[y])&&y<i?c++:(s^=!(y-i|c%2)<<c/2,c=1,y=--i););
s,a[51],y,i;main(c){
	for(;~scanf("%d",a+i)?y=++i:(y=a[y])&&y<i?c++:(s^=!(y-i|c%2)<<c/2,c=1,y=--i););
	s=!puts(s?"No":"Yes");
}

122B

17/02/28追記

for(;~scanf("%d",a+i)?y=++i:(y=a[y])&&y<i?c++:(s^=!(y-i|c%2)<<c/2,c=1,y=--i););
//真偽を入れ替えてカッコを外す
for(;~scanf("%d",a+i)?y=++i:!(y=a[y])|y/i?s^=!(y-i|c%2)<<c/2,c=1,y=--i:c++;);
//真偽をry
for(;~scanf("%d",a+i)?y=++i:!(y=a[y])|y/i?s^=(y==i&c%2<1)<<c/2,c=1,y=--i:c++;);
//cの初期値を変更
for(;~scanf("%d",a+i)?y=++i:!(y=a[y])|y/i?s^=(y==i&c)<<c/2,c=0,y=--i:++c;);

ということで

s,a[51],c,i;main(y){
	for(;~scanf("%d",a+i)?y=++i:!(y=a[y])|y/i?s^=(y==i&c)<<c/2,c=0,y=--i:++c;);
	s=!puts(s?"No":"Yes");
}

118B