yukicoder : No.1854 Limited Bubble Sort

こちらは考察軽め実装重め。
https://yukicoder.me/problems/no/1854

問題

1～NのPermutationである、1-originの数列Pが与えられる。
P[i]!=iかつP[i+1]!=i+1であるiを選びswapする、という処理を繰り返し、Pを昇順にソートできるか。
できるならその手順を示せ。

解法

初期状態でP[i]=iの部分は動かせないので、それらで区切られた区間毎に考える。

以下、P[i]!=iの場合を考える。
再帰的に、後ろからそろえることを考える。
今P[m]=Nとする。

• P[m+1]...P[N]が、P[i]=i+1を満たす場合
  • P[m]とP[m+1]をswap、P[m+1]とP[m+2]をswap...と繰り返すと、P[m...N]が[m..N]と一致するので、以下残り(m-1)要素を考えればよい。
• P[m+1]...P[k-1]が、P[i]=i+1を満たし、P[k]!=k+1である場合
  • P[m]...P[k]の中にmとなるものはない。よって、これらをswapすることでP[m]=mになることはない。
  • まずswapを繰り返し、P[k]をP[m+1]まで持ってくる。次にP[m]をP[k]までもってこよう。そうすると、P[k]とP[m]をswapすることができるし、これによってP[i]=iとなってしまい以後動かせなくなるものは生じない。

int T,N,P[505];
vector<int> ret;

void go(int x) {
	assert(P[x]!=x&&P[x+1]!=x+1);
	swap(P[x],P[x+1]);
	ret.push_back(x);
}

void hoge(int L,int R) {
	if(R<L) return;
	
	int cur=0;
	int i,j;
	for(i=L;i<=R;i++) {
		if(P[i]==i) {
			hoge(L,i-1);
			hoge(i+1,R);
			return;
		}
		if(P[i]<L||P[i]>R) {
			ret.push_back(-1);
			return;
		}
		if(P[i]==R) cur=i;
	}
	
	if(L+1==R) {
		go(L);
		return;
	}
	
	for(i=cur+1;i<=R;i++) {
		if(P[i]!=i-1) {
			for(j=i-1;j>cur;j--) go(j);
			go(cur);
			for(j=cur+1;j<i;j++) go(j);
			cur=i;
		}
	}
	while(cur<R) go(cur++);
	hoge(L,R-1);
	
	
		
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>P[i+1];
		ret.clear();
		hoge(1,N);
		
		if(count(ALL(ret),-1)) {
			cout<<-1<<endl;
		}
		else {
			FOR(i,N) assert(P[i+1]==i+1);
			cout<<ret.size()<<endl;
			FORR(r,ret) cout<<r<<" ";
			cout<<endl;
		}
	}
}

まとめ

なんかうまくできそうってことはわかるけど、綺麗に書くのは意外に難しい。