2018 TCO Algorithm: Medium. Resistance

,

solution

$2^P$通り全て試して間に合う。$O(2^PM)$。

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
using namespace std;
class Resistance { public: vector<double> spyProbability(int P, int S, vector<string> missions); };

vector<double> Resistance::spyProbability(int P, int S, vector<string> missions) {
    vector<int> masks;
    for (string const & mission : missions) if (mission[0] == 'F') {
        int acc = 0;
        REP (i, P) if (mission[i + 1] == '1') {
            acc |= 1 << i;
        }
        masks.push_back(acc);
    }
    vector<int> num(P);
    int den = 0;
    REP (spies, 1 << P) {
        if (__builtin_popcount(spies) != S) continue;
        bool valid = true;
        for (int mask : masks) {
            if (not (spies & mask)) {
                valid = false;
                break;
            }
        }
        if (valid) {
            REP (i, P) if (spies & (1 << i)) {
                num[i] += 1;
            }
            den += 1;
        }
    }
    if (den == 0) return vector<double>();
    vector<double> prob(P);
    REP (i, P) prob[i] = num[i] / (double)den;
    return prob;
}