SRM645div2Hard:JanuszInTheCasino

問題文を理解するのが一番難しかった。

問題:TopCoder Statistics - Problem Statement

解法:確率を最大化するためには,なるべくいろいろなフィールドに人を同じ人数だけ分散させるのが良い。そのようにシミュレーションして得られるのが答え。
以下ソースコード

map<pair<ll, int>, double> mp;

double dfs(ll n, int m, int k) {
    if (n <= 0) return 0;
    if (k == 0) return 1;
    if (mp.find(make_pair(n, k)) != mp.end()) return mp[make_pair(n, k)];
    ll p = n/m;
    ll q = n%m;
    return mp[make_pair(n, k)] = 1.*(m-q)/m*dfs(n-p, m, k-1) + 1.*q/m*dfs(n-p-1, m, k-1);
}

class JanuszInTheCasino {
public:
    double findProbability(long long n, int m, int k) {
        mp.clear();
        if (m == 1) return 0;
        return dfs(n, m, k);
    }
};