yukicoder No.482 あなたの名は

問題はこちら
No.482 あなたの名は - yukicoder

「1～Nの置換が与えられたとき、その逆置換がちょうどK個の互換の積で書けるか判定せよ」という問題
まずは与えられた置換を最も少ない個数の互換の積で書くときの個数を考える
これは先頭から順に貪欲に交換していくことでわかる（互いに素な巡回置換の積に分解していることと本質的に同じ）
この個数をxとすれば、「x≦K かつ x≡K mod 2」がYESであるための必要十分条件であることが置換の偶奇性からわかる

int main(){
	long a[200010],k,x=0;
	int i,t,n;
	scanf("%d%ld",&n,&k);
	for(i=1;i<=n;i++)scanf("%d",a+i);
	for(i=1;i<=n;i++)while(a[i]!=i){
		//a[i]とa[a[i]]をswap。後述
		t=a[i];
		a[i]=a[t];
		a[t]=t;
		x++;
	}
	puts(x<=k&&x%2==k%2?"YES":"NO");
	return 0;
}

上のプログラムでは次のような手順によってswapが行われていく

2 5 6 7 1 3 4
↓1番目に2があるので、これを正しい位置に置くために2番目とswapする
5 2 6 7 1 3 4
↓1番目に5があるので、これを正しい位置に置くために5番目とswapする
1 2 6 7 5 3 4
↓1番目に1があり、これは正しい位置
↓2番目に2があり、これは正しい位置
↓3番目に6があるので、これを正しい位置に置くために6番目とswapする
1 2 3 7 5 6 4
↓3番目に3があり、これは正しい位置
↓4番目に7があるので、これを正しい位置に置くために7番目とswapする
1 2 3 4 5 6 7
4,5,6,7番目が正しい位置にあることがそれぞれ確かめられるのでこれで完成

明らかにkを直接減らしていけばxはいらない。
また、kが-1になった時点でループを抜けることにすれば、「kが0以上かつ偶数か？」を「kが偶数か？」にまとめられるのでそのようにしようと考えながら縮めて

for(i=1;i<=n&&k>=0;i++)while(a[i]!=i)t=a[i],a[i]=a[t],a[t]=t,k--;
for(i=1;a[i]&&k>=0;)a[i]-i?t=a[i],a[i]=a[t],a[t]=t,k--:++i;
for(i=1;a[i]-i?t=a[i],a[i]=a[t],a[t]=t,~--k:a[++i];);

読み込みをいつも通り工夫して

long a[1<<18];j=1;
main(i){
	for(;~scanf("%ld",a-i--););
	for(;a[j]-j?i=a[j],a[j]=a[i],a[i]=i,~--*a?a[++j];);
	j=!puts(*a&1?"NO":"YES");
}

ループ圧縮

long a[1<<18],j=1;
main(i){
	for(;~scanf("%ld",a-i--)?:j-a[j]?i=a[j],a[j]=a[i],a[i]=i,~--*a:a[++j];);
	j=!puts(*a&1?"NO":"YES");
}

ポインタ

long a[1<<18],*p=a+1;
main(i){
	for(;~scanf("%ld",a-i--)?:p-a-*p?i=*p,*p=a[i],a[i]=i,~--*a:*++p;);
	*a=!puts(*a&1?"NO":"YES");
}

122B