kojingharangの日記

Codeforces #212 Div2 C. Insertion Sort

23:14 |

• 0〜N-1のpermutation配列Aを挿入ソートする。ソートの前に任意の２要素を交換できるとき、swapの回数の最小値と、そうなる２要素の個数を求める。
• 2≦N≦5000

• 何もしないときの転倒数を求めておいて、
• i＜j なる i, j in [0, N) それぞれに対して、予め A[i], A[j] を交換したときの転倒数の増減を求めれば答えがわかる。

• 増減は
• A[i], A[i+1], ..., A[j-1], A[j] (最初)
• A[j]をA[i]の前に持ってきたときの増減は、Σ(A[k]＜A[j]の個数)-(A[k]＞A[j]の個数) for k in [i, j)
• A[j], A[i], A[i+1], ..., A[j-1] (A[j]をA[i]の前に移動)
• A[i]をA[j-1]の後ろに持ってきたときの増減は、Σ(A[k]＞A[i]の個数)-(A[k]＜A[j]の個数) for k in [i+1, j)
• A[j], A[i+1], ..., A[j-1], A[i](A[i]をA[j-1]の後ろに移動)

• 普通にやるとO(N^3)なのでなんとかO(N^2)にしたい
• wf[r][l] ... A[r]をA[l]の前に持ってきたときの転倒数の増減
• wf[l][r] ... A[l]をA[r]の後ろに持ってきたときの転倒数の増減
• とO(N^2)で事前に計算しておく。
• と、A[i], A[j]を交換したときの増減は wb[r][l] + wf[l][r-1] で求まるので全体として O(N^2)

• accepted

int main() {
	ll N;
	while(cin>>N) {
		VI w(N);
		REP(i, N) cin>>w[i];
		VVI wb(N, VI(N)), wf(N, VI(N));
		REP(i, N) for(int k=i-1;k>=0;k--) wb[i][k] = wb[i][k+1] + (w[k]>w[i]) - (w[k]<w[i]);
		REP(i, N) for(int k=i+1;k<N;k++) wf[i][k] = wf[i][k-1] + (w[k]<w[i]) - (w[k]>w[i]);
		int Max=0;
		int co=0;
		RANGE(r, 1, N) REP(l, r) {
			Max = max(Max, wb[r][l]+wf[l][r-1]);
		}
		RANGE(r, 1, N) REP(l, r) {
			if(Max==wb[r][l]+wf[l][r-1]) co++;
		}
		int def=0;
		RANGE(i, 1, N) {
			int j=i;
			while(j>0 && w[j] < w[j-1]) {
				swap(w[j], w[j-1]);
				def++;
				j--;
			}
		}
		cout<<def-Max<<" "<<co<<endl;
	}
	
	return 0;
}

ツイートする