C - ゲーマーじゃんけん dwangoプログラミングコンテスト

C: ゲーマーじゃんけん - dwangoプログラミングコンテスト | AtCoder

N人の中からK人が勝つのにかかる回数の期待値が分かれば解ける。
N人の内、k人が勝つ確率をp(N,K)、N人のじゃんけんが終わる回数の期待値をENとして

整理してやって

P(N,K)を求めるには、N人の手の種類全部につき、それらが何通りあるかを調べ、
その手で勝つ人数（引き分けならN人が勝つ)をiとして、P(N,i)に加算してやり、最後に全体の通りで割ればいい。
それぞれの手の個数がgcpの時の通り

Submission #3884323 - dwangoプログラミングコンテスト | AtCoder

vd fact(128);
vd dp(128); //　　i人をさばく時の期待値回数
double comb(int g, int c, int p) {
    return fact[g + c + p] / fact[g] / fact[c] / fact[p];
}
double dfs(int x) {
    if (dp[x] >= 0) return dp[x];
    //gcpの数について、それぞれ何通りあるかしらべ
    //j人が勝つなら、tori[j] += する
    vd per(128); //　i人が勝つ時の通り
    rep(g, x + 1) {
        rep(c, x + 1 - g) {
            int p = x - g - c;
            vi te;
            if (g)te.pb(g);
            if (c)te.pb(c);
            if (p)te.pb(p);
            sort(te);
            int rare = te[0];
            switch (count(all(te), rare)) {
                case 1:
                    per[rare] += comb(g, c, p);
                    break;
                case 2:
                    per[rare] += comb(g, c, p);
                    break;
                case 3:
                    per[x] += comb(g, c, p);
                    break;
            }
        }
    }
    double zen = sum(per);
    for (auto &&a :per)a /= zen;
    double res = 1;
    rep(i, 1, x) res += per[i] * dfs(i);
    res /= 1 - per[x];
    return dp[x] = res;
}
signed main() {
    cin >> N;
    fact[0] = 1;
    rep(i, 1, 128)fact[i] = fact[i - 1] * i;
    fill(dp, -1);
    dp[1] = 0;
    cout << dfs(N) << endl;
    return 0;
}