Codeforces #740 Div1 : C. Bottom-Tier Reversals

本番さほど苦労せず解けているな。
https://codeforces.com/contest/1558/problem/C

問題

1～NのPermutation Aが与えられる。
Aの奇数長のprefixを指定し、反転するという作業を繰り返してAを昇順にソートしたい。
可能なら、5N/2回以下での達成手順を示せ。

解法

奇数長prefixによる反転では、移動前後のindexの偶奇は変わらない。
そのため、初期状態と終了状態で同じ値のindexの偶奇が異なる場合、解なし。
それ以外の場合解がある。

後ろから2要素ずつ、2要素あたり5手でそろえていこう。そうすれば全体で5N/2手で済む。

A中の(まだソートを終えていない)最大値をX、次に大きな値をYとする。
以下の手順で揃える。

• Xの位置までを反転し、Xを先頭に持ってくる
• Yの手前の位置までを反転し、Yの手前にXを持ってくる
• Yの次の位置までを反転し、先頭3要素を*,Y,Xの順になるようにする
• 先頭3要素を判定し、先頭3要素をX,Y,*の順になるようにする
• XがA[X]に収まるように反転する。

int T;
int N;
int A[2050];
int R[2050];
vector<int> ret;
int ON;

void debug() {
	int i;
	FOR(i,ON) cerr<<A[i];
	cerr<<endl;
}
void go(int id) {
	ret.push_back(id+1);
	reverse(A,A+id+1);
	int i;
	FOR(i,id+1) R[A[i]]=i;
	//debug();
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		ON=N;
		int ng=0;
		FOR(i,N) {
			cin>>A[i];
			A[i]--;
			if(A[i]%2!=i%2) ng=1;
			R[A[i]]=i;
		}
		if(ng==1) {
			cout<<-1<<endl;
			continue;
		}
		
		ret.clear();
		
		while(N>1) {
			if(A[N-1]!=N-1||A[N-2]!=N-2) {
				go(R[N-1]);
				go(R[N-2]-1);
				go(R[N-2]+1);
				go(R[N-1]);
				go(N-1);
			}
			N-=2;
		}
		
		
		FOR(i,ON) assert(A[i]==i);
		cout<<ret.size()<<endl;
		FORR(v,ret) cout<<v<<" ";
		cout<<endl;
	}
}

まとめ

これ任意の順列に対し最小回数で達成するアルゴリズムがあるとしたら、回数のオーダーどのぐらいなんだろ。