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; } }