CSAcademy Round #17 : C. To Front - To Back

似たようなのCodeforcesで見たような気がするけど思い出せない。
https://csacademy.com/contest/round-17/#task/to-front-to-back

問題

1～NのPermutationを成す数列が与えられる。
この数列に対し、任意の要素を先頭または末尾に移動させる、という処理を繰り返す。
処理回数を最小にして、数列を昇順にソートするにはどの順で処理を行えばよいか。

解法

要素を外に移動することはできても中に挿入することはできない。
よって、数列の部分列のうち、連番となる最長の部分列を残し、それ以外の要素を外側に移動させるとよい。

int N;

int X[101010];
int R[101010];

int cnt[101010];
int id=-1;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i];
		R[X[i]]=i;
	}
	
	id=1;
	cnt[1]=1;
	for(i=2;i<=N;i++) {
		if(R[i]>R[i-1]) {
			cnt[i]=cnt[i-1]+1;
			if(cnt[i]>cnt[id]) id=i;
		}
		else {
			cnt[i]=1;
		}
	}
	
	x=id-cnt[id]+1;
	cout<<(x-1)+(N-id)<<endl;
	for(i=x-1;i>=1;i--) cout<<i<<" "<<0<<endl;
	for(i=id+1;i<=N;i++) cout<<i<<" "<<1<<endl;
}

まとめ

Google Code Jam 2014 Round2 Bが頭に思い浮かんだ。
解法異なるけどね。