kmjp's blog

競技プログラミング参加記です

Codeforces #176 Div1. A. Lucky Permutation

Codeforces

今後はDiv2 A・Bは省略することにします。

ではCF176。
この回は参加し、A,Bが何とか解けてまぁまぁの順位に。
http://codeforces.com/contest/286/problem/A

問題

大きさNのPermutationとは、1～Nを１回ずつ含む整数列である。
ここで、Lucky Permutationとは、i番目(1<=i<=N)の要素p_iについて、 p_{p_i} = N-i+1を満たすPermutationとする。

Nが与えられたとき、大きさNのLucky Permutationが作れるならそれを答えよ。

問題

CF175が終わったのにまだPermutationネタか。

色々条件を満たすPermutationを作ってみる。
例えばN=8だと2 8 4 6 3 5 1 7になる。よく見ると、2 8 - - - - 1 7の様に4つで組になる。
ここから、1<=i<=i/4について以下であることがわかる。これは p_{p_i} = N-i+1を満たす。

  • p_{2i-1} = 2i
  • p_{2i} = N - 2i + 2
  • p_{N-2i+1} = 2i-1
  • p_{N-2i+2} = N - 2i + 1

Nが4の倍数でない場合、余りが問題。
余りが2または3の時、これらの余った要素を p_{p_i} = N-i+1を満たすように作れないので、Lucky Permutationは作れない。
余りが１個の場合、真ん中の要素を p_{N/2+1} = N/2+1にすればよい。

int N;
int P[100001];

void solve() {
	int f,r,i,j,k,l, x,y,ma,num,nt;
	
	N=GETi();
	
	if(N%4==2 || N%4==3) {
		_P("%d\n",-1);
		return;
	}
	
	ZERO(P);
	
	if(N%4==1) P[N/2+1]=N/2+1;
	
	FOR(i,N/4) {
		P[i*2+1]=(i+1)*2;
		P[i*2+2]=N+2-P[i*2+1];
		P[N-i*2-1]=P[i*2+1]-1;
		P[N-i*2]=P[i*2+2]-1;
	}
	
	FOR(i,N) {
		if(i!=N-1) _P("%d ",P[i+1]);
		else _P("%d\n",P[i+1]);
	}
	
	return;
}

まとめ

本番自分は色々条件を満たす数列を作って上記条件を見つけた。
人によっては、p_1を全通り仮定して、残りを順々に決めてる人とか、少ない要素で総当たりして法則を見つけてる人もいたっぽいね。