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); } };