Codeforces 339E Three Swaps

問題

長さがnの数列
1 2 3 4 ... n-1 nがある。

この数列に対して3回以下、以下のような操作を行った。
l, rを選びaの区間[l, r]の順番を反転させる。

結果の数列が与えられるとき、操作の仕方としてありえるものをどれか一通り出力せよ。

制約条件

n≦1000

方針

数列を1...nに戻す方法を全探索すればいい。
数列を、連続する部分はブロックとして見て、ブロックの途中で切る操作を考えないようにすると、計算量的に余裕になる。

が、実はブロックの途中で切らないと辿りつけない状態がある。
ブロックの途中で切るのは、1回だけでいいので、ブロックの左端の一個隣であらかじめブロックを分割しておくと通る。

ソースコード

int n, a[1000], L[3], R[3];
vi pos;
vector<pi> iv;

void rec(int step){
	bool ok = 1;
	rep(i, iv.size()) if((iv[i].second > 1 && iv[i].first % 2) ||
		(i && iv[i-1].first > iv[i].first)) ok = 0;
	if(ok){
		cout << step << endl;
		for(int i = step-1; i >= 0; i--) cout << L[i] << " " << R[i] << endl;
		exit(0);
	}
	if(step == 3) return;
	
	rep(r, iv.size()) rep(l, r + 1){
		if(l == r && iv[l].second == 1) continue;
	
		reverse(iv.begin() + l, iv.begin() + r + 1);
		for(int i = l; i <= r; i++) iv[i].first ^= 1;
		L[step] = 1; R[step] = 0;
		rep(i, l) L[step] += iv[i].second;
		rep(i, r+1) R[step] += iv[i].second;
		
		rec(step + 1);
		
		reverse(iv.begin() + l, iv.begin() + r + 1);
		for(int i = l; i <= r; i++) iv[i].first ^= 1;
	}
}

int main(){
	cin >> n;
	rep(i, n) cin >> a[i];
	
	rep(i, n){
		if(i == 0 || abs(a[i] - a[i-1]) > 1){
			pos.pb(i);
		}
	}
	pos.pb(n);
	for(int i = pos.size()-2; i >= 0; i--) pos.pb(pos[i]+1);
	sort(all(pos));
	pos.erase(unique(all(pos)), pos.end());
	
	rep(i, pos.size() - 1){
		int sz = pos[i+1] - pos[i];
		if(a[pos[i]] - 1 == a[pos[i] + 1]) iv.pb(mp(a[pos[i+1] - 1] * 2 + 1, sz));
		else iv.pb(mp(a[pos[i]] * 2, sz));
	}
	
	rec(0);
	
	return 0;
}