Codeforces ECR #007 : D. Optimal Number Permutation

最近CFが不調気味だが、なぜか異常に出来のよかった回。
http://codeforces.com/contest/622/problem/D

問題

1～Nが2回ずつ登場する数列Aを考える。
整数iがA中に出てくる添え字を小さい順にX[i],Y[i]とし、その差をD[i]=Y[i]-X[i]とする。。

が最小となるAを構築せよ。

解法

各iに対し、sumの中を0にすることを考える。
D[1],D[2],D[3]...は順にN-1,N-2,N-3....となるようにしたい。
またD[N]の値はsumの値に寄与しないので、Nは何処に置いても良い。
よって：

• Nが奇数の場合
  • 1,3,5,...(N-2),N,(N-2),...,5,3,1,N,2,4,6,...(N-2),(N-2),...6,4,2と並べればよい。
• Nが偶数の場合
  • 1,3,5,...(N-1),(N-1),...,5,3,1,N,2,4,6,...(N-2),N,(N-2),...6,4,2と並べればよい。

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	vector<int> V;
	if(N%2==0) {
		for(i=1;i<N;i+=2) V.push_back(i);
		for(i=N-1;i>0;i-=2) V.push_back(i);
		for(i=2;i<N;i+=2) V.push_back(i);
		V.push_back(N);
		for(i=N-2;i>0;i-=2) V.push_back(i);
		V.push_back(N);
	}
	else {
		for(i=1;i<N;i+=2) V.push_back(i);
		for(i=N;i>0;i-=2) V.push_back(i);
		V.push_back(N);
		for(i=2;i<N;i+=2) V.push_back(i);
		for(i=N-1;i>0;i-=2) V.push_back(i);
	}
	FORR(r,V) _P("%d ",r);
	_P("\n");
}

まとめ

Educational…？