SRM 680 div1 easy: BearFair

問題

TopCoder Statistics - Problem Statement

解法

dp[b][even][odd] = (b 以下の数の set で, 偶数の数が even で奇数の数が odd であるようなものは存在するか) とします。

普通に dp して dp[b][n/2][n/2] が true かどうか見るだけですね。

int dp[1010][55][55];
int check[1010];

class BearFair {
public:
    string isFair(int n, int b, vector <int> upTo, vector <int> quantity) {
        vector<pii> P;
        int q = upTo.size();
        for (int i = 0; i < q; i++) P.emplace_back(upTo[i], quantity[i]);
        sort(P.begin(), P.end());
        for (int i = 0; i < q-1; i++) {
            if (P[i].first == P[i+1].first) {
                if (P[i].second != P[i+1].second) return "unfair";
            }
            if (P[i].second > P[i+1].second) return "unfair";
        }
        memset(check, -1, sizeof(check));
        for (int i = 0; i < q; i++) check[P[i].first] = P[i].second;
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        for (int i = 0; i < 1010; i++) {
            for (int even = 0; even < 55-1; even++) {
                for (int odd = 0; odd < 55-1; odd++) {
                    if (dp[i][even][odd] == 0) continue;
                    if ((i+1)%2 == 0) {
                        if (check[i+1] != -1) {
                            if (even+odd == check[i+1]) dp[i+1][even][odd] = 1;
                            else if (even+odd+1 == check[i+1]) dp[i+1][even+1][odd] = 1;
                        } else {
                            dp[i+1][even][odd] = 1;
                            dp[i+1][even+1][odd] = 1;
                        }
                    } else {
                        if (check[i+1] != -1) {
                            if (even+odd == check[i+1]) dp[i+1][even][odd] = 1;
                            else if (even+odd+1 == check[i+1]) dp[i+1][even][odd+1] = 1;
                        } else {
                            dp[i+1][even][odd] = 1;
                            dp[i+1][even][odd+1] = 1;
                        }
                    }
                }
            }
        }
        return (dp[b][n/2][n/2] == 1) ? "fair" : "unfair";
    }
};