解いた問題

2/04/2012

SRM475 Div1 Easy

300
全部試す。

シュミレーションで挑んで泣きたくなった。
でも、よく考えたらそうでもなかった。
うさぎがはみ出ることがない以上、偶数インデックスと奇数インデックスのそれぞれに1匹残るかどうかになる。
class RabbitStepping {
public:
  double getExpected(string F, int r)
  {   
    double sum = 0;
    double cnt = 0;
    for (int bit = 0; bit < (1 << F.size()); ++bit) {
      if (__builtin_popcount(bit) == r) {      
        ++cnt;
        int n[2];
        n[0] = n[1] = 0;
        for (int i = 0; i < F.size(); ++i) {
          if (bit & (1 << i)) n[i % 2] ^= 1;
        }
        sum += n[0] + n[1];
      }
    }

    return sum / cnt;
  }
};

0 件のコメント :

コメントを投稿