Codeforces #204 Div1. E. Jeff and Permutation

2000ptとはいえなぜか本番あっさりとけた問題。
http://codeforces.com/contest/351/problem/E

問題

整数列Pが与えられる。
各要素は、任意に符号反転できる。
この時、P[i]>P[j]となるような(i,j)のペアの数を最小化せよ。

問題

まずは少し面倒な解き方から。

絶対値が大きい順に符号を決めていく。
絶対値が小さい数値の符号がどうであれ、絶対値が大きい数値の符号で両者の大小関係が決まる。

よって絶対値が大きい順に符号を+と-選んだ場合のペア数をDPで求める。
問題は、絶対値が同じ値が複数あるとき。
数列の手前にある値が+で、後にある値が-だとその分ペアの数が増える。
よって、同じ絶対値の要素を処理するとき、+で選んだ数を覚えながらDPしなければならない。

int N;
int P[5005];
pair<int,int> PP[5005];
int dpdp[2][5002];

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>N;
	FOR(i,N) cin>>P[i];
	FOR(i,N) P[i]=abs(P[i]);
	FOR(i,N) PP[i]=make_pair(-P[i],i);
	sort(PP,PP+N);
	l=50000000;
	r=0;
	FOR(i,N+1) dpdp[0][i]=1<<30;
	dpdp[0][0]=0;
	
	FOR(i,N) {
		int cur=i%2,tar=(i+1)%2;
		int mi=0,pl=0;
		j=PP[i].second;
		FOR(x,N+1) dpdp[tar][x]=1<<30;
		
		FOR(x,j) if(P[x]<P[j]) mi++;
		for(x=j+1;x<N;x++) if(P[x]<P[j]) pl++;
		if(PP[i].first==l) {
			FOR(x,N+1) {
				dpdp[tar][x] = min(dpdp[tar][x], dpdp[cur][x]+x+mi);
				dpdp[tar][x+1] = min(dpdp[tar][x+1], dpdp[cur][x]+pl);
			}
		}
		else {
			
			FOR(x,N+1) {
				dpdp[tar][0] = min(dpdp[tar][0], dpdp[cur][x]+mi);
				dpdp[tar][1] = min(dpdp[tar][1], dpdp[cur][x]+pl);
			}
			l=PP[i].first;
		}
	}
	
	x=1<<30;
	FOR(y,N+1) x=min(x,dpdp[N%2][y]);
	cout << x << endl;
}

これ、後で他人の解答みて気づいたのだが、実は同じ絶対値の数が複数あるとき、手前を+、後を-にすることはない。
絶対値がXの要素が2個あるとき、(A個のX以下の要素):X:(B個のX以下の要素):X:(C個のX以下の要素)という数列について、2つのXの符号によって得られるペア数を考える。

1. 2つのXが両方+ : B+2C
2. 2つのXが両方- : 2A+B
3. 手前が+、後が- : A+2B+C+1
4. 手前が-、後が+ : A+C

3は4より確実に多いので、構成3をとることはなく、プラスの数を数える必要はない。
よってシンプルにこう書ける。

int N;
int P[5005];

void solve() {
	int f,r,i,j,k,l, x,y;
	
	cin>>N;
	FOR(i,N) cin>>P[i];
	FOR(i,N) P[i]=abs(P[i]);
	l=0;
	FOR(i,N) {
		x=y=0;
		FOR(j,N) {
			if(j<i && P[i]>P[j]) x++;
			if(j>i && P[i]>P[j]) y++;
		}
		l+=min(x,y);
	}
	cout << l << endl;
	return;
}

まとめ

想定解はどっちなんだろ。
後者ならBIT使えばO(N logN)でも解けるし前者なのかな？