お疲れ様でした。
http://yukicoder.me/problems/no/475
問題
N人がyukicoderのAdvent Calendar Contestに挑んでいる。
最終日を前にN人のスコアはA[i]である。
難易度Sの問題に対し、Writerは無条件でスコア100S点、それ以外はR番目に解いた人はのスコアを得る。
Writer以外の各人の順位は、(1~(N-1))位それぞれ当確率で生じるものとする。
最終日Writerが難易度Sの問題を出すとき、Writerが優勝する確率を求めよ。
解法
Writer以外の参加者のスコアを降順に並べよう。
各参加者について、何位以下であればWriterのスコアを上回らないか、二分探索などで求めよう。
(降順に並べた後)x番目の参加者がy位以下であればWriterを上回らないとする。x番未満の参加者はもちろんy位以下であるはずなので、(N-y-x)/(N-x)の確率でx番の人はWriterを上回らない。
この確率を各参加者について掛け合わせていけなよい。
int N,S,I; ll A[101010],L[101010]; ll my; int U[101010]; ll sc(int r) { return 50LL*S+500LL*S/(8+2*r); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>S>>I; FOR(i,N) { cin>>A[i]; if(I==i) { my=A[i]+100*S; i--; N--; I=-1; } } sort(A,A+N); reverse(A,A+N); double ret=1; FOR(i,N) { ll left=my-A[i]; if(left < sc(N)) return _P("0\n"); x = N; for(j=20;j>=0;j--) if(x-(1<<j)>=1 && sc(x-(1<<j))<=left) x -= (1<<j); int ok=N-x+1; if(ok<i) return _P("0\n"); ret *= (ok-i)*1.0/(N-i); } _P("%.12lf\n",ret); }
まとめ
No.465はまだ元論文を理解していないのでまた後日…。