この回はダメダメでした。
https://csacademy.com/contest/round-61/task/unstable-merge-sort/
問題
N要素の数列Aをマージソートで並べ替える。
なお、マージソートでは2つのソート済み配列をマージする処理が含まれるが、その際どちらの配列も次の要素の候補の値が同じ場合、等確率で片方を選択するとする。
元要素がソート後何番目に来るか、期待値を求めよ。
解法
1要素ずつソート後の行先とその確率を求めよう。
今Aのi番目の要素がソート後どこに行くかを考える。
A[i]より小さい要素より後ろ、大きい要素より手前に来るのは確定している。
よってA[i]と同じ値の要素のうち何番目に来るか、またその確率を求めればよい。
マージソートの過程では、処理対象の部分列にA[i]と等しい要素ががm個ある場合、m要素の配列を保持しよう。
配列のj番目の要素は、A[i]がそのうち何番目に来うるかの確率を示す。
マージソート過程で2つの部分列をマージすることになるが、この場合もこの2つの配列をマージしよう。
2つの配列長を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); } }
まとめ
これは解けててもよかったな。