問題はこちら
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
