読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

yukicoder : No.302 サイコロで確率問題 (2)

yukicoder

勉強になった。
http://yukicoder.me/problems/190

問題

1~6の目が等確率で出る普通のサイコロをN回投げる。
目の和がL以上R以下になる確率を求めよ。

解法

Nが小さい場合、O(N^2)のDP解法で正確に求めることができる。

問題はNが大きい場合である。
幸い許容誤差はさほど小さくないので、大数の法則を信じて統計的に処理しよう。

Nが大きいとき、目の和がある値になる確率は正規分布 N(\mu,\sigma)に近づく。

N回サイコロを振る時の出目の和の期待値は \mu = \frac{7}{2}N標準偏差 \sigma = \sqrt{\frac{35}{12}N}である。
よって上記μ, σに対し f(x)=N(\mu,\sigma)をL~Rの範囲で積分する。

Writer解は実際に区分求積を行っているようだ。
また、正規分布 - Wikipediaにもあるとおり、正規分布の累積分布関数g(x)は \displaystyle g(x) = \int_{-\infty}^x f(x) = \frac{1}{2}\left( 1+erf(\frac{x-\mu}{\sqrt{2\sigma^2}})\right)で与えられる。
幸いC++ではerf関数がライブラリに入っているので、g(R)-g(L)を容易に計算できる。

ll N,L,R;

double from[50606],to[50606];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L>>R;
	L=min(6*N,max(N,L));
	R=min(6*N,R);
	
	if(N<=8000) {
		double di=1/6.0;
		ZERO(from);
		from[0]=1;
		FOR(i,N) {
			ZERO(to);
			for(j=i;j<=6*i;j++) for(x=1;x<=6;x++) to[j+x] += from[j]*di;
			swap(from,to);
		}
		_P("%.12lf\n",accumulate(from+L,from+R+1,0.0));
	}
	else {
		double ave=N*3.5;
		double var=N*35.0/12;
		
		_P("%.12lf\n",(erf((R+0.5-ave)/(sqrt(2*var)))-erf((L-0.5-ave)/(sqrt(2*var))))/2);
	}
}

まとめ

本番はなんか大ざっぱに求める方法があるんだろうと思いつつ、正規表現+数値積分から持ってくるとは気づかなかった。
あとerfなんて関数が標準ライブラリにあるとも知らなかった。

広告を非表示にする