Hatena::Grouptopcoder

tsubosakaの日記

2011-12-27

SRM 526.5 Div1 500

23:02

二項分布の期待値と分散の式を使えばすごい簡単だった

各rangeにおけるgridごとのbeautyの期待値を計算する。10000 * 50 * 50なので間に合う。rangeの10000のところは値が変わるところだけ計算すればいいので工夫すれば50^3でいける。


public class MagicBlizzard {
  class Snow{
    long range , amount;
    double exp , exp2;
    Snow(long r , long a){
      range = r;
      amount = a;
      double prob = 1.0 / (2.0 * range + 1.0) / (2.0 * range + 1.0);
      // Binom(prob,amount)に従う確率変数Xに関してE[X],E[X^2]を計算する
      exp = amount * prob;
      // 分散の公式 E[X^2] = E[X]^2 + Var[X]を利用
      exp2 = exp * exp + amount * prob * (1 - prob);
    }
  }
  // 距離rangeにあるgridにおけるbeautyの期待値を返す
  private double calcExp(Snow[] ss, long range) {
    double expect = 0;
    for(int i = 0 ; i < ss.length ; ++i){
      if(ss[i].range < range)continue;
      expect += ss[i].exp2;
    }
    for(int i = 0 ; i < ss.length ; ++i){
      if(ss[i].range < range)continue;
      for(int j = i + 1 ; j < ss.length ; ++j){
        if(ss[j].range < range)continue;
        expect += 2 * ss[i].exp * ss[j].exp;
      }
    }
    return expect;
  }

  public double expectation(int[] range, int[] amount) {
    Snow ss[] = new Snow[range.length];
    for(int i = 0 ; i < ss.length ; ++i){
      ss[i] = new Snow(range[i] , amount[i]);
    }
    int rmax = 0;
    for(int r : range)
      rmax = Math.max(r, rmax);
    double expect = calcExp(ss, 0);
    for(long r = 1 ; r <= rmax ; ++r){
      expect += 8 * r * calcExp(ss, r);
    }    
    return expect;
  }
}