SRM 518 Div2 Hard CoinReversing

問題

http://community.topcoder.com/stat?c=problem_statement&pm=11473&rd=14543
表向きに置かれたN枚のコインと要素数Kの配列a[]が与えられる。ターンi（0-indexed）ではコインをa[i]枚ランダムに選んで裏表をひっくり返す、という動作をKターンまで行った時、表になっているコインの枚数の期待値を求めよ。

やりかた

Editorialを参考にしました。

あるコインがターンi終了時にの確率で表になっているとすると、次ターンで表になっている確率は

となる。つまり（ターンi終了時に裏向きのコインが次ターンで表向きになる確率）+（ターンi終了時に表向きであるコインが次ターンでも表向きになる確率）である。

これでこのコインが試行後に表向きになる期待値がもとまった。ランダムにコインが選ばれるので、各コインについての事象は独立である。よって和の期待値は期待値の和になるので各コインについて上の計算を行ってその和を求めればいい。しかし、どのコインも期待値が等しいので単純に上の結果をN倍すればいい。

以下ソース。

class CoinReversing {
public:
  double expectedHeads(int N, vector <int> a) {
    double ret = 1.0;
    for(int i = 0; i < (int)a.size(); i++){
      double q = (double)a[i] / N;
      ret = ret * (1 - q) + (1 - ret) * q;
    }
    return ret * N;
  }
}

連続するa[i]枚のコインをひっくり返す、という誤読をやらかして再帰で書いていた。馬鹿だなあ。

SRM455~554のDiv2 Hardを解いているのだけれど、このあたりでどうしようもなく中だるみしている。やってもわからないor正解できないということがあまりに続くため意気阻喪中みたい。ただ2週目に入ればペースも上がって、やる気も出てくると思う。