Facebook Hacker Cup 2016 Round 2 Carnival Coins

問題

https://www.facebook.com/hackercup/problem/1627951250755660/

解法

まず, 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;
}