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

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

問題

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

解法

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

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

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

N回サイコロを振る時の出目の和の期待値は、標準偏差はである。
よって上記μ, σに対しをL～Rの範囲で積分する。

Writer解は実際に区分求積を行っているようだ。
また、正規分布 - Wikipediaにもあるとおり、正規分布の累積分布関数g(x)はで与えられる。
幸い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なんて関数が標準ライブラリにあるとも知らなかった。