Codeforces #212 Div2. C. Insertion Sort

コンテスト練習ということで、レートつかないけどDiv2本番参加。
本番A,B,Cは解けたけどWA連発、Dはpretest通ってsystest通らず、Eはそもそも解けず、と微妙な出来。
Eはともかく、それ以外はさらっと通したかった。
Div2の割にCが難しめだね。
http://codeforces.com/contest/362/problem/C

問題

問題ページに示す通りのバブルソートプログラムが与えられる。

0～(N-1)からなるN要素のpermutation数列Aが与えられたとき、事前に2つの要素を入れ替えた後に昇順バブルソートを行った場合、バブルソート処理中でのswap回数を最小化したい。
swap回数の最小値と、その最小値を得られる最初の入れ替えの要素対の組み合わせ数を答えよ。

解法

前処理を行ったうえで、各要素対を入れ替えた場合のswap回数を求める。
まず、元のバブルソートにおけるswap回数は、数列中の要素において、それより手前に大きな数字がある数、である。

ここで、0～(N-1)の各数iにおいて、その数が数列中j番目に来た時にそれより手前0～(j-1)にそれより大きい数および小さい数が来る個数を数えておく。
2つの要素を入れ替えた場合、swap回数の増減はこの事前計算した各位置より手前にある大きな数・小さな数の個数をもとに計算できる。

A[x]番目と、それよりあとのA[y]を入れ替える場合、A[x]＜A[y]だと後のswap回数はむしろ増加するので入れ替える意味はない。
よってA[x]＞A[y]の場合だけ考えればよい。

• A[x]が後ろのy番目に移動することで、x+1～y-1番目にあるA[x]より小さい数の個数だけswapは減少する。
  • また、x+1～y-1番目にあるA[x]より大きい数の個数だけswapは増加する。
• 逆にA[y]が手前のx番目に移動することで、x+1～y-1番目にあるA[y]より小さい数の個数だけswapは増加する。
  • また、x+1～y-1番目にあるA[y]より大きい数の個数だけswapは減少する。

上記処理は事前計算の値を使えばO(1)で計算できるので、全体でO(N^2)。

int N;
int D[5020];
int num[5020][5020];
int num2[5020][5020];
int sum=0;
void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>D[i];
	
	FOR(i,N) for(j=1;j<N;j++) {
		num[i][j]=num[i][j-1];
		num2[i][j]=num2[i][j-1];
		if(D[j-1]>i) num[i][j]++;
		if(D[j-1]<i) num2[i][j]++;
	}
	
	FOR(i,N) sum+=num[D[i]][i];
	
	int mi=1<<29;
	k=0;
	FOR(x,N) for(y=x+1;y<N;y++) {
		if(D[x]<D[y]) continue;
		i=sum;
		i+=num[D[x]][y]-num[D[x]][x];
		i-=num2[D[x]][y]-num2[D[x]][x];
		i+=num[D[y]][x]-num[D[y]][y];
		i-=num2[D[y]][x]-num2[D[y]][y];
		
		if(i<mi) k=0,mi=i;
		if(i==mi) k++;
	}
	_P("%d %d\n",mi,k);
}

まとめ

本番何度かWAしたけど、こういうのミスなく解けるようにしたいなぁ。