AtCoder Beginner Contest ABC008 C - コイン

問題へのリンク

解説

公式解説とは異なる方針でACしたので記録を残しておきます。

まず、いわゆる主客転倒（寄与ゲー）と呼ばれる問題だと捉えます。 今回求めたいのは、の並びのうち、表のコインの数の期待値ですが、 これを期待値ではなく数え上げの問題として認識します。 つまり、表のコインの枚数を数え上げ、最後にで割れば期待値の計算ができます。

これを、あるコインが表になる場合の数を足し合わせることで計算します。

あるコインが表になるのは、そのコインより左のコインの中に の約数が偶数個ある場合です。

まず、コイン以外での約数の個数をとします。

コインが位置にあって、その左に個コインがある場合を数え上げればよく(は偶数)、これはcombinationとpermutation、階乗の計算を前計算すれば解くことができます。

1. の約数個から左に置くコイン個を選び、
2. 選んだ約数個を左への並べ方が通り（場所を選んで並べるイメージ）、
3. 残りの約数個を右への並べ方が通り（場所を選んで並べるイメージ）、
4. 約数以外の並べ方が（場所は上で確定しているので、並べるだけ）通り。

計算量はです。

実装

• 提出へのリンク

ところでこの階乗の計算で誤差ってどこまで許容されるんですかね（わかっていない顔）。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)

int main() {
    cout << fixed << setprecision(20);
    int N;
    cin >> N;
    vector<int> C(N);
    rep(i, N)cin >> C[i];
    vector<int> cnt(N,0);
    rep(i,N)rep(j,N){
        if(i == j)continue;
        if(C[j]%C[i] == 0)cnt[j]++;
    }

    long double kai = 1;
    for(int i = 1; i <= N; i++)kai /= i;
    vector<long double> fact(N+1);
    fact[0] = kai;
    rep(i,N)fact[i+1] = fact[i] * (i+1);

    auto comb = [&](int a, int b) -> long double{
        if(a == 0 || b == 0)return 1;
        if(b > a)return 0;
        return fact[a] / fact[a-b] / fact[b] * kai;
    };
    auto perm = [&](int a, int b) -> long double{
        if(a == 0 || b == 0)return 1;
        if(b > a)return 0;
        return fact[a] / fact[a - b];
    };

    long double ans = 0; 
    // あるコインiが場所jにいて
    // 自分より左にk個、右にcnt[i] - k個おくときの場合の数
    // kは偶数のみ
    rep(i,N)rep(j,N){
        for(int k = 0; k <= j && k <= cnt[i]; k+=2){
            int S = cnt[i];
            if(k > j)continue;
            if(S-k > N-1-j)continue;
            long double tmp = comb(S,k) * perm(j,k) * perm(N-1-j,S-k) * fact[N-1-S];
            ans += tmp;
        }
    }
    cout << ans << endl;
}

公式解説

• 公式解説へのリンク

公式の解説では、もっと簡単に問題を捉えています。 まず、期待値の線形性を考えれば、コインごとの期待値の足し合わせが答えになることがわかります。

コインについて考えると、期待値を計算するのであれば、とても簡潔に考えることができます。 コインの位置について、約数の並べの中でどの位置にあるかを考えます。この位置に関して、共通して現れる計算として、約数の並べ方と約数以外の並べ方があります。これらはコインが約数の並べの中でどの位置になるかに依存しません。まず約数を並べて、位置を選び、その後約数以外を挿入すると考えるとわかりやすいでしょう。よって、約数の個数のみを考慮すれば良いことになります。

考える順番を変えるだけでかなり楽に計算することができました。