Codeforces #324 Div2 E. Anton and Ira

直感で書いたのが通ってしまった。
http://codeforces.com/contest/584/problem/E

問題

1～Nのpermutationである２つの数列p,sが与えられる。
数列の要素p[i]とp[j]は、位置の差|i-j|のコストをかけて交換できる。
pをsにするのに必要な最小コストと、交換手順を求めよ。

解法

以下の問題の経験があるととっつきやすい。
AtCoder ARC #043 : C - 転倒距離 - kmjp's blog
東京工業大学プログラミングコンテスト2015: I - そーっとソート - kmjp's blog

まず、sが0～(N-1)の昇順となるようp,sの数字を採番しなおそう。
そうするとpを昇順にする問題となった。

pを端から、すなわちp[N-1]=N-1、p[N-2]=N-2…と順番に揃えることを考える。
p[i+1]～p[N-1]はすでにそろっていてp[i]=iにそろえることを考える。
今p[x]=iとすると、p[i]=iにするためにはどうやっても|i-x|のコストがかかる。
また、その際一発でp[x]とp[i]を交換しても良いが、xとiの間にあるyに対し、p[x]とp[y]を交換し、その後p[y]とp[i]を交換してもコストが変わらない。
この場合、同じコストでもp[y]を左側に持って行くことができる。

どうせあとでp[y]をxより左に持ってこなければいけない。
すなわちp[y]＜xなら、このようにp[x]をp[i]に移動する過程で順次そのようなp[y]を左に移動していくと良い。

この手順では、最初から目的地より後ろにある数字が目的地の前に来ることはないし、逆に最初目的地の手前にある数字は目的地の後ろに行くことはないので、コストは最小と言える。

int N;
int P[2020],Q[2020],R[2020];
vector<pair<int,int>> ret;
int C;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i];
	FOR(i,N) cin>>Q[i], R[Q[i]]=i;
	FOR(i,N) P[i]=R[P[i]];
	
	int cur;
	while(N) {
		FOR(cur,N) if(P[cur]==N-1) break;
		
		while(cur<N-1) {
			for(x=cur+1;x<=N-1;x++) if((P[x]<x && P[x]<=cur) || x==N-1) {
				C += x-cur;
				ret.push_back({x+1,cur+1});
				swap(P[x],P[cur]);
				cur=x;
			}
		}
		assert(P[N-1]==N-1);
		N--;
	}
	
	_P("%d\n",C);
	_P("%d\n",ret.size());
	FORR(r,ret) _P("%d %d\n",r.first,r.second);
	
}

まとめ

今回はD,Eの実装がぬるめで助かった。