tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

SRM 526.5 MagicBlizzard

統計学の知識を使う良問。

問題:
「-R <= x,y <= Rを満たす格子点(x,y)のうちどこかに雪を1個降らせる、をP回繰り返す」
という情報が50個以下与えられる。このとき、各マスに(降った雪の個数)^2の合計の期待値を求めよ。

解法:
まず、試してみるとそれぞれのマスにおいて(降った雪の個数)^2を求めて、足せばよいことは分かる。
確率変数Xをあるマスに降った雪の個数とすると、求めたいのはE(X^2)。
統計学で広く知られている有名な事実 " V(X) = E(X^2) - {E(X)}^2 "を用いると、この値は
V(X) + {E(X)}^2と等しいことがわかる。 E(X)は独立に計算することで自明に求まる。
また、独立なもの達x1,...,xnに対しては、V(x1+x2+...+xn)=V(x1)+V(x2)+...+V(xn)であることと、
確率pのものが起きたら1/起きないなら0、という事象での分散はp(1-p)であることを考慮し、
後は降りうる組が同じものをまとめて計算すればよい。

import java.util.*;
public class MagicBlizzard{
	public double expectation(int[]a,int[]b){
		int n=a.length;
		int[]c=new int[n];
		int[]d=new int[n];
		for(int i=0;i<n;i++){
			c[i]=a[i];
		}
		Arrays.sort(c);
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(a[i]==c[j]){
					d[j]+=b[i];
					break;
				}
			}
		}
		double ret=0;
		for(int i=n-1;i>=0;i--){
			double v=0;
			double e=0;
			for(int j=i;j<n;j++){
				double p=1.0/(1+c[j]*2)/(1+c[j]*2);
				v+=(double)d[j]*p*(1.0-p);
				e+=(double)d[j]*p;
			}
			ret+=(v+e*e)*((1+c[i]*2)*(1+c[i]*2)-(i==0?0:(1+c[i-1]*2)*(1+c[i-1]*2)));
			System.out.println(v+" "+e+" "+(v+e*e)+" "+((1+c[i]*2)*(1+c[i]*2)-(i==0?0:(1+c[i-1]*2)*(1+c[i-1]*2))));
		}
		return ret;
	}
}