Codeforces #197 Div2. E. Three Swaps

解いた人は少ないけど、さほど難しくない。
http://codeforces.com/contest/339/problem/E

問題

1～Nのpermutationで構成される数列Aと整数k(0<=K<=3)が与えられる。
この数列に対し、A[L]～A[R]までの要素の順序をひっくり返す、という処理を最大K回まで行い、この数列を1～Nの昇順の数列にしたい。
そのようなL,Rの選び方を答えよ。

解法

N自体は最大1000と大きいが、ひっくり返す処理はK回までしかできないので、初期状態のAは昇順または降順の部分数列が高々計2K+1個にしかならない。

N要素の数列と考えると面倒なので、昇順または降順の部分数列がいくつか連結していると考える。
すると各部分数列の初期値と終了値のpairが2K+1個あるだけのデータ構造ができる。
これが昇順の部分数列1個になれば題意を満たすことになる。

あえて昇順または降順になっている部分数列について、真ん中を取ってひっくり返すことはますます部分数列の数を増すのでよくない。
よって、2K+1個の部分数列の初期値または終了値計(4K+2)個から、LとRを総当たりで選んでひっくり返していけばよい。
K<=3なので(4K+2)から２個選ぶことを３回行っても、何とか時間に間に合う。

void dfs(vector<pair<int,int> > P, vector<pair<int,int> > C) {
	int i,x,y;
	vector<pair<int,int> > P2;
	vector<int> P3;

	FOR(i,P.size()) {
		if(!P2.empty() && abs(P2[P2.size()-1].second-P[i].first)==1) P2[P2.size()-1].second=P[i].second;
		else P2.push_back(P[i]);
	}
	
	if(P2.size()==1 && P2[0].first==1) {
		_P("%d\n",C.size());
		FOR(i,C.size()) _P("%d %d\n",C[C.size()-1-i].first,C[C.size()-1-i].second);
		exit(0);
	}
	if(C.size()>=3) return;
	
	y=1;
	FOR(x,P2.size()) P3.push_back(y),P3.push_back(y+abs(P2[x].second-P2[x].first)),y+=1+abs(P2[x].second-P2[x].first);
	FOR(x,P3.size()) for(y=x+1;y<P3.size();y++) {
		if(P3[x]==P3[y]) continue;
		if(x%2 && P3[x]==P3[x-1]) continue;
		if(y%2==0 && P3[y+1]==P3[y]) continue;
		C.push_back(make_pair(P3[x],P3[y]));
		if(x%2==0 && y%2==1) {
			P=P2;
			for(i=x/2;i<=y/2;i++) P[i]=make_pair(P2[x/2+y/2-i].second,P2[x/2+y/2-i].first);
		}
		else  {
			P.clear();
			FOR(i,x/2) P.push_back(P2[i]);
			if(x%2==0 && y%2==0) {
				P.push_back(make_pair(P2[y/2].first,P2[y/2].first));
				for(i=y/2-1;i>=x/2;i--) P.push_back(make_pair(P2[i].second,P2[i].first));
				P.push_back(make_pair(P2[y/2].first+((P2[y/2].second>P2[y/2].first)?1:-1),P2[y/2].second));
			}
			else if(x%2==1 && y%2==0) {
				P.push_back(make_pair(P2[x/2].first,P2[x/2].second+((P2[x/2].second>P2[x/2].first)?-1:1)));
				P.push_back(make_pair(P2[y/2].first,P2[y/2].first));
				for(i=y/2-1;i>=x/2+1;i--) P.push_back(make_pair(P2[i].second,P2[i].first));
				P.push_back(make_pair(P2[x/2].second,P2[x/2].second));
				P.push_back(make_pair(P2[y/2].first+((P2[y/2].second>P2[y/2].first)?1:-1),P2[y/2].second));
			}
			else {
				P.push_back(make_pair(P2[x/2].first,P2[x/2].second+((P2[x/2].second>P2[x/2].first)?-1:1)));
				for(i=y/2;i>=x/2+1;i--) P.push_back(make_pair(P2[i].second,P2[i].first));
				P.push_back(make_pair(P2[x/2].second,P2[x/2].second));
			}
			for(i=y/2+1;i<P2.size();i++) P.push_back(P2[i]);
		}
		dfs(P,C);
		C.pop_back();
	}
	
}

void solve() {
	int f,i,j,k,l, x,y,N;
	vector<pair<int,int> > P;
	
	cin>>N;
	FOR(i,N) cin>>x,P.push_back(make_pair(x,x));
	dfs(P,vector<pair<int,int> >());
}

まとめ

解法自体は難しくないのだが、pairの処理にfirstとかsecondとか繰り返し使ったら文字数がやたら増えた。
ノーヒントで解けきれてよかった。