CodeChef Ciel and Quiz Game - mayoko’s diary

問題

N 問の問題が与えられる。それぞれの正答率は P[i] である。この中から K 問を選んで K-1 問正解する確率を最大化したい。K 問の選び方を構成せよ。

解法

前の GCJ の問題と似ています。

mayokoex.hatenablog.com

これと同じように P をソートして前半と後半からうまいぐらいに選ぶと良いです。

const int MAXN = 55;
double dp[MAXN][MAXN], dpr[MAXN][MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int N, K;
        cin >> N >> K;
        vector<pair<double, int> > P;
        for (int i = 0; i < N; i++) {
            int p;
            cin >> p;
            P.emplace_back(p/100., i);
        }
        sort(P.begin(), P.end());
        for (int i = 0; i <= N; i++) for (int j = 0; j <= N; j++) {
            dp[i][j] = 0;
            dpr[i][j] = 0;
        }
        dp[0][0] = dpr[0][0] = 1;
        for (int i = 0; i < N; i++) for (int j = 0; j <= i; j++) {
            dp[i+1][j+1] += dp[i][j]*P[i].first;
            dp[i+1][j] += dp[i][j]*(1-P[i].first);
            dpr[i+1][j+1] += dpr[i][j]*P[N-1-i].first;
            dpr[i+1][j] += dpr[i][j]*(1-P[N-1-i].first);
        }
        double maxP = -1;
        int maxK = -1;
        for (int k = 0; k <= K; k++) {
            double tmp = 0;
            for (int i = 0; i <= K-1; i++) {
                tmp += dp[k][i] * dpr[K-k][K-1-i];
            }
            if (maxP < tmp) {
                maxP = tmp;
                maxK = k;
            }
        }
        vi ans;
        for (int i = 0; i < maxK; i++)
            ans.push_back(P[i].second);
        for (int i = 0; i < K-maxK; i++) 
            ans.push_back(P[N-1-i].second);
        int sz = ans.size();
        for (int i = 0; i < sz; i++) 
            cout << ans[i]+1 << (i == sz-1 ? "\n" : " ");
    }
    return 0;
}