Codeforces #696 Div2 E. What Is It?

本番はずいぶんギリギリに通してるな…。
https://codeforces.com/contest/1474/problem/E

問題

1～NのPermutation Pを、昇順に並べ替えることを考える。
P[j]=iであるi,jの対を1つ選び、P[i]とP[j]をswapするという手順を繰り返す。
この際、(i-j)^2のコストがかかる。

Nが与えられたとき、コストが最悪値となるP及び操作順を求めよ。

解法

自分は実験ゲーで解いてしまった。
Nが偶数の時、以下のように[(N-1),1,2,....(N/2-1),N,(N/2+1),....,(N-2),N/2]のように並べる。

9 1 2 3 4 10 6 7 8 5 

その後、jとして1や10を沢山使うようにしてコストを嵩上げしていこう。

5 10
4 10
3 10
2 10
9 1
8 1
7 1
6 1
10 1

Nが奇数の時も大体同じ。

int T,N;

int P[202020],A[202020];
int R[202020];
ll ret;
vector<pair<int,int>> V;
void hoge(int i,int j) {
	assert(P[j]==i);
	swap(P[i],P[j]);
	R[P[j]]=j;
	R[P[i]]=i;
	ret+=1LL*(i-j)*(i-j);
	V.push_back({i,j});
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	/*
	vector<int> A,B;
	N=7;
	for(i=1;i<=N;i++) A.push_back(i);
	int ma=0;
	do {
		vector<int> B;
		for(i=1;i<=N;i++) B.push_back(i);
		do {
			
			for(i=1;i<=N;i++) P[i]=A[i-1],R[P[i]]=i;
			V.clear();
			ret=0;
			FORR(b,B) hoge(b,R[b]);
			if(ret==38) {
				FORR(a,A) cout<<a;
				cout<<" ";
				FORR(a,B) cout<<a;
				cout<<endl;
			}
			ma=max(ma,(int)ret);
		
		} while(next_permutation(ALL(B)));
	} while(next_permutation(ALL(A)));
	cout<<ma<<endl;
	return;
	*/
	cin>>T;
	while(T--) {
		cin>>N;
		
		V.clear();
		ret=0;
		
		if(N==2) {
			cout<<1<<endl<<"2 1"<<endl<<1<<endl<<"2 1"<<endl;
			continue;
		}
		if(N==3) {
			cout<<5<<endl<<"2 3 1"<<endl<<2<<endl<<"1 3"<<endl<<"3 2"<<endl;
			continue;
		}
		
		if(N%2==1) {
			for(i=1;i<=N/2;i++) P[i+1]=i;
			P[N]=N/2+1;
			for(i=N/2+2;i<N-1;i++) P[i+1]=i;
			P[1]=N-1;
			P[N/2+2]=N;
			for(i=N/2+2;i<N-2;i++) P[i+1]=i;
			FOR(i,N) A[i+1]=P[i+1], R[P[i+1]]=i+1;
			FOR(i,N/2) hoge(P[N],N);
			FOR(i,N/2) hoge(P[1],1);
		}
		else {
			for(i=1;i<=N/2-1;i++) P[i+1]=i;
			P[N]=N/2;
			for(i=N/2+1;i<N-1;i++) P[i+1]=i;
			P[1]=N-1;
			P[N/2+1]=N;
			FOR(i,N) A[i+1]=P[i+1], R[P[i+1]]=i+1;
			for(i=N/2+1;i<N-2;i++) P[i+1]=i;
			for(i=N/2;i>=2;i--) hoge(P[N],N);
			FOR(i,N/2) hoge(P[1],1);
		}
		
		cout<<ret<<endl;
		FOR(i,N) cout<<A[i+1]<<" ";
		cout<<endl;
		cout<<V.size()<<endl;
		FORR2(a,b,V) cout<<a<<" "<<b<<endl;
	}
}

まとめ

ずいぶん手間取った。