Rockethon 2015 : C. Second price auction

Bよりこちらの方が簡単かな…。
http://codeforces.com/contest/513/problem/C

問題

N人の人がオークションを行う。
各人はL[i]～R[i]のいずれかの金額を等確率で選択し、オークションに挑む。

落札者は当然最大金額を提示した人だが、実際に支払いをする額は２番目に提示された金額と等しくなる。
落札額の期待値を答えよ。

解法

落札額xを総当たりし、落札額がxとなる確率を掛け合わせればよい。
落札額がxとなるのは以下のいずれかである。

• xより高い金額を１人、xちょうどの金額を１人以上提示した場合
• xより高い金額を提示した人がおらず、xちょうどの金額を２人以上提示した場合

幸い人数が少ないので、各人の提示価格が「xより高い」「xちょうど」「xより低い」の3^N通りを総当たりし、上記条件を満たす組み合わせにおいて、そのような金額提示が成される確率を求めることができる。

int N;
int L[6],R[6];
int p3[7];
double ret=0;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>L[i]>>R[i];
	p3[0]=1;
	FOR(i,6) p3[i+1]=p3[i]*3;
	
	for(i=1;i<=10000;i++) {
		for(int mask=0;mask<p3[N];mask++) {
			int hoge[3]={};
			FOR(x,N) hoge[mask/p3[x]%3]++;
			if(hoge[2]>1) continue;
			if(hoge[1]==0) continue;
			if(hoge[1]==1 && hoge[2]==0) continue;
			double tmp=1;
			
			FOR(x,N) {
				int rr=R[x],ll=L[x];
				if(mask/p3[x]%3==0) rr=min(rr,i-1);
				if(mask/p3[x]%3==1) ll=max(ll,i),rr=min(rr,i);
				if(mask/p3[x]%3==2) ll=max(ll,i+1);
				if(rr-ll+1<=0) tmp=0;
				else tmp *= (rr-ll+1.0)/(R[x]-L[x]+1);
			}
			ret += tmp*i;
		}
	}
	_P("%.12lf\n",ret);
	
}

まとめ

シンプルだが現実にありそうでなかなか面白い問題。