東京工業大学プログラミングコンテスト2015 : I - そーっとソート

こちらも無駄に手間がかかる解法です。
http://ttpc2015.contest.atcoder.jp/tasks/ttpc2015_i

問題

1～Nのpermutationである数列A[i]が与えられる。
これらの数列の２要素A[i],A[j]は、|i-j|=A[i]または|i-j|=A[j]の時swapできる。
swap100000回以内でA[i]を1～Nが順に並んだ状態にできるか。
できるならそのswap順を示せ。

解法

Editorialの解法が簡潔でびっくり。
A[N]とA[N-A[N]]をswapすることを繰り返すと、いずれA[N]=Nになるので、Nをデクリメントして続ければいいだけらしい。

自分の解法はもっと手間がかかるけど、うまくいく理屈は分かりやすいと思うので一応紹介。
最大値であるA[N]=Nをそろえて、どんどんNを小さくしていく点は想定解とおなじ。
ではA[N]=Nをどう実現するか。

A中1となる要素は隣とのswapが常に可能であることを用いる。
A中Nより1の方が後ろにあるなら、1を前の要素とswapを繰り返すことで、Nを1つ右に動かすことができる。
ここで、1がNの左に来てしまうので、またなんとか1をNの右に持っていきたい。
A[x]=Nであるとして、A[x+1]～A[N]の間にx以下のものが1つはあるはずである。
たとえばA[y]=z (z≦x)を1個選ぶ。
1をまた隣同士swapしてA[y-z]に持って来れば、1とzが交換できるのでまた1をNの右側に持ってこれた。

あとは上記処理を繰り返すだけ。O(N^3)ぐらいの処理でうまくいくと思う。

int N;
int A[55],pos[55];

vector<pair<int,int>> R;

void doswap(int s,int t) {
	R.emplace_back(min(s,t),max(s,t));
	swap(A[s],A[t]);
	pos[A[t]]=t;
	pos[A[s]]=s;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i+1], pos[A[i+1]]=i+1;
	while(N>1) {
		while(A[N]!=N) {
			if(pos[1]<pos[N]) {
				for(i=pos[N]+1;i<=N;i++) if(i-A[i]>=1) break;
				
				while(i-A[i]>=pos[N]) {
					x=A[i];
					doswap(i,i-A[i]);
					i -= x;
				}
				
				if(i<pos[N]) continue;
				if(i-A[i]<1) continue;
				
				int tar=i-A[i];
				while(pos[1]<tar) doswap(pos[1],pos[1]+1);
				while(pos[1]>tar) doswap(pos[1],pos[1]-1);
				
				doswap(pos[1],i);
			}
			
			while(pos[1]>pos[N]) doswap(pos[1]-1,pos[1]);
		}
		N--;
	}
	_P("%d\n",R.size());
	FORR(r,R) _P("%d %d\n",r.first,r.second);
	
}

まとめ

自分はこの隣同士swapを駆使するから「そーっとソート」なのかと思ったけど、想定解がそうじゃないのでびっくりした。
どこらへんが「そーっと」なのだろうか。
ちなみに問題はTTPCで解いた範囲ではこれが一番好みでした。