yukicoder : No.475 最終日 - Writerの怠慢

お疲れ様でした。
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はまだ元論文を理解していないのでまた後日…。