kmjp's blog

競技プログラミング参加記です

Codeforces #1040 : Div1. B. Stay or Mirror

いまいちふるわないなぁ。
https://codeforces.com/contest/2129/problem/B

問題

1~NのPermutation Pが与えられる。
N要素の整数列Aを、以下のように作る。

  • A[i]はP[i]か2N-P[i]のいずれか

Aの転倒数の最小値を求めよ。

解法

P[i]<P[j]の時、A[j]がP[j]か2N-P[j]のどちらかであるというのはA[i]に影響しない。
A[i]をP[i]と2N-P[i]のどちらにするかだけで定まる。

そこでP[i]の大きい順に定めて行くとよい。
A[i]をP[i]と2N-P[i]のどちらか転送数の少ない方に合わせて取る。

int T,N;
int P[5050];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>P[i];
		ll ret=0;
		for(i=1;i<=N;i++) {
			FOR(j,N) if(P[j]==i) k=j;
			x=y=0;
			FOR(j,N) if(P[j]!=-1&&j!=k) {
				if(j<k) {
					x++;
				}
				else {
					y++;
				}
			}
			ret+=min(x,y);
			P[k]=-1;
		}
		cout<<ret<<endl;
		
	}
		
}

まとめ

これO(NlogN)で行ける気がするけど、なんでO(N^2)を許容するような入力なんだろ。