Codeforces #485 B. Petr and Permutations

一瞬戸惑ったが割と簡単。
http://codeforces.com/contest/986/problem/B

問題

1～Nのpermutationが与えられる。
この数列は、1～Nが順に並んだ数列を3N回か(7N+1)回のいずれかの回数、「２要素を選んでswap」を繰り返したものである。
実際のswap回数はどちらであるか求めよ。

解法

まず、与えられた数列を元の数列に戻すのに最低何回かかるかを求めよう。
さらに余分なswapを行っても同じように元の数列に戻せるためには、余分なswap回数が偶数でなければならない。
よってswap回数の偶奇が決まる。3Nと(7N+1)はどちらかが偶数でどちらかが奇数なので、合致する方を答えよう。

int N;
int A[1010101];
int vis[1010101];

int hoge(int cur) {
	int ret=1;
	vis[cur]=1;
	if(vis[A[cur]]==0) ret+=hoge(A[cur]);
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	scanf("%d",&N);
	FOR(i,N) {
		scanf("%d",&A[i]);
		A[i]--;
	}
	int ret=0;
	FOR(i,N) if(vis[i]==0) ret+=hoge(i)-1;
	if(ret%2==N%2) cout<<"Petr"<<endl;
	else cout<<"Um_nik"<<endl;
	
}

まとめ

結構変な解を投げてる人がいたな。