Google Code Jam 2017 Round 1C: C. Core Training

,

https://codejam.withgoogle.com/codejam/contest/dashboard?c=3274486#s=p2

solution

$N = K$の場合は、最も$p_i$の小さいコア$i$を強化するのがよい。 $N \ne K$の場合は、$A, B$を全て試して次のようにする: 元々の$p_i$の大きい順に、上から$A$個を$p_i = 1.0$に、残りの中で上から$B$個を抜き出してきてそれらに対して$N = K$の場合と同様にする。

kmjpさんの解説も見て: http://kmjp.hatenablog.jp/entry/2017/05/03/1100

note

「$+ 0.0001$した場合をそれぞれに試してみて最も改善されるものを採用」という貪欲ではWAだった。editorialで次のように言及されているので通ると思うのだがなぜだろう。

It is also possible to arrive at the correct answers via other methods such as gradient descent.

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < int(n); ++ (i))
#define ALL(x) begin(x), end(x)
using namespace std;
template <class T> inline void chmax(T & a, T const & b) { a = max(a, b); }

double run_dp(int k, vector<int> const & p) {
    vector<double> cur, prv;
    cur.assign(k + 1, 0);
    cur[0] = 1;
    for (int p_i : p) {
        cur.swap(prv);
        cur.assign(k + 1, 0);
        REP (j, k) {
            cur[j + 1] += prv[j] * (p_i / 10000.0);
            cur[j]     += prv[j] * ((10000 - p_i) / 10000.0);
        }
        cur[k] += prv[k];
    }
    return cur[k];
}
double solve(int n, int k, const int u, vector<int> const & p) {
    double answer = - INFINITY;
    REP (a, n + 1) {
        REP3 (b, a, n + 1) {
            int v = u;
            vector<int> q = p;
            sort(q.rbegin(), q.rend());
            REP (i, a) {
                while (v and q[i] < 10000) {
                    -- v;
                    ++ q[i];
                }
            }
            if (a < b) {
                while (v and q[b - 1] < 10000) {
                    int i = min_element(q.begin() + a, q.begin() + b) - q.begin();
                    -- v;
                    ++ q[i];
                }
            }
            chmax(answer, run_dp(k, q));
        }
    }
    return answer;
}

int read_fixed() {
    int a, b; scanf("%d.%d", &a, &b);
    return a * 10000 + b;
}
int main() {
    int t; scanf("%d", &t);
    REP (i, t) {
        int n, k; scanf("%d%d", &n, &k);
        int u = read_fixed();
        vector<int> p(n);
        REP (i, n) p[i] = read_fixed();
        double answer = solve(n, k, u, p);
        printf("Case #%d: %.6lf\n", i + 1, answer);
fprintf(stderr, "Case #%d: %.6lf\n", i + 1, answer);
    }
    return 0;
}