CSAcademy Round #61 : E. Unstable Merge Sort

この回はダメダメでした。
https://csacademy.com/contest/round-61/task/unstable-merge-sort/

問題

N要素の数列Aをマージソートで並べ替える。
なお、マージソートでは２つのソート済み配列をマージする処理が含まれるが、その際どちらの配列も次の要素の候補の値が同じ場合、等確率で片方を選択するとする。

元要素がソート後何番目に来るか、期待値を求めよ。

解法

１要素ずつソート後の行先とその確率を求めよう。
今Aのi番目の要素がソート後どこに行くかを考える。
A[i]より小さい要素より後ろ、大きい要素より手前に来るのは確定している。
よってA[i]と同じ値の要素のうち何番目に来るか、またその確率を求めればよい。

マージソートの過程では、処理対象の部分列にA[i]と等しい要素ががm個ある場合、m要素の配列を保持しよう。
配列のj番目の要素は、A[i]がそのうち何番目に来うるかの確率を示す。
マージソート過程で２つの部分列をマージすることになるが、この場合もこの２つの配列をマージしよう。

２つの配列長をp,qとすると、新たな配列長は(p+q)である。
マージソート過程ではこの(p+q)個をどの順で組み合わせるかを考えなければならないが、前者からx個、後者からy個取り除いた状態になる確率は基本的になので、これで重みづけしつつマージして以降。

int N;
int A[606];
vector<double> V[606];
double C[605][605];
double CS[605][605];

vector<double> merge_sort(int L,int R) {
	if(R<L) return vector<double>();
	if(L==R) return V[L];
	int M=(L+R)/2;
	
	auto S=merge_sort(L,M);
	auto T=merge_sort(M+1,R);
	if(S.empty()) return T;
	if(T.empty()) return S;
	int a=S.size(),b=T.size();
	vector<double> U(a+b);
	int x,y;
	FOR(x,a+1) FOR(y,b+1) {
		if(x==a&&y==b) continue;
		if(x==a) {
			double p=1-CS[x+y][a];
			U[x+y]+=p*T[y];
		}
		else if(y==b) {
			double p=1-CS[x+y][b];
			U[x+y]+=p*S[x];
		}
		else {
			double p=C[x+y][x];
			U[x+y]+=p*(S[x]+T[y])*0.5;
		}
	}
	return U;
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	C[0][0]=CS[0][1]=1;
	for(x=1;x<=602;x++) {
		FOR(y,602) {
			C[x][y]+=C[x-1][y]*0.5;
			if(y) C[x][y]+=C[x-1][y-1]*0.5;
			CS[x][y+1]=CS[x][y]+C[x][y];
		}
	}
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	
	FOR(i,N) {
		double ret=1;
		FOR(j,N) {
			V[j].clear();
			if(A[i]==A[j]) V[j].push_back(i==j);
			if(A[j]<A[i]) ret+=1.0;
		}
		vector<double> v=merge_sort(0,N-1);
		FOR(j,v.size()) ret+=j*v[j];
		_P("%.12lf\n",ret);
		
	}
	
}

まとめ

これは解けててもよかったな。