Facebook Hacker Cup 2016 Round 2 Carnival Coins
解法
まず, C[n][k] = (n 枚のコインを投げた時 k 枚表が出る確率) を求めます。これはコンビネーションの nCr を求めるのと同じような dp で出来ます。
問題で必要になるのは C[n] = (n 枚のコインを投げた時 K 枚以上表が出る確率) なので, C[n][k] からこれを求めます。
あとは dp するだけです。dp[n] = (n 枚コインが残っている時, 景品をもらえる個数の最大期待値) とすると, コインを K 〜 n 枚のうちどれだけ使うか, という場合分けができるので, それらのうち, 最も期待値が高いものを選びます。
const int MAX = 3333; double dp[MAX]; double C[MAX][MAX]; double memo[MAX]; int N, K; double dfs(int n) { double& ret = dp[n]; if (ret >= 0) return ret; ret = 0; for (int i = K; i <= n; i++) { double p = memo[i]; double tmp = 0; tmp += p*(1+dfs(n-i)); tmp += (1-p)*dfs(n-i); ret = max(ret, tmp); } return ret; } void solve(int T) { double p; cin >> N >> K >> p; C[0][0] = 1; for (int n = 1; n <= N; n++) { C[n][0] = C[n-1][0]*(1-p); for (int k = 1; k <= N; k++) { C[n][k] = C[n-1][k-1]*p+C[n-1][k]*(1-p); } } for (int i = K; i <= N; i++) { memo[i] = 0; for (int j = K; j <= i; j++) memo[i] += C[i][j]; } for (int i = 0; i <= N; i++) dp[i] = -1; printf("Case #%d: %.9lf\n", T, dfs(N)); } int main() { int T; cin >> T; for (int t = 1; t <= T; t++) { solve(t); } return 0; }