読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

SRM 680 Div.1 Easy BearFair

Div.1 Easy 4題目。

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14129

以下の条件を満たす集合が存在するか判定せよ。

  • 要素は互いに異なる正の整数

  • 素数  n は偶数

  • 集合は  n / 2 個の偶数と  n / 2 個の奇数からなる

  • 要素はすべて  1 以上  b 以下

  •  1 以上  upTo[i] の要素が  quantity[i] 個

制約

 2 \leq n \leq 50,  n は偶数

 n \leq b \leq 1000

 1 \leq q \leq 50 ( upTo,  quantity の要素数)

解法

mayokoさんのブログを参考にしました(ほんとお世話になります)

mayokoex.hatenablog.com

DP。 dp[i][e][o] = (i以下の数から偶数をe個, 奇数をo個選べるか) として、dp[b][n/2][n/2]がtrueとなるか調べればよい。

ただしその前に”明らかに間違っている”ケースは省かなければならない。upTo と quantityをpairにしてソートしたとき、upTo[i]が同じなのにquantity[i]が異なるものがあればアウト。また、upto[i]とquantityの大小関係が逆転しているようなケースもダメ。

  • 解答例: C++

配るDPをしているので、添え字の上限から1引くことに注意。(これでSystem Test 1回落ちた)

class BearFair {
    public:
    string isFair(int n, int b, vector<int> upTo, vector<int> quantity) {
        int q = upTo.size();
        vector<pii> P;
        rep(i, q) P.pb(upTo[i], quantity[i]);
        sort(all(P));

        rep(i, q - 1) {
            if (P[i].first == P[i + 1].first
                && P[i].second != P[i + 1].second) {
                return "unfair";
            }
            if (P[i].second > P[i + 1].second) {
                return "unfair";
            }
        }

        // dp[b][e][o] = b以下の数から、重複なくe個の偶数とo個の奇数を選べるか
        bool dp[1010][55][55];
        rep(i, 1010) rep(j, 55) rep(k, 55) dp[i][j][k] = false;
        dp[0][0][0] = true;

        // check[b] = クマの集合に含まれるb以下の数の個数(指定がなければ-1)
        int check[1010];
        memset(check, -1, sizeof(check));
        rep(i, q) check[P[i].first] = P[i].second;

        // 配るDP(i, e, oの組が存在するマスから次の遷移先に配っていく)
        // !! +1にアクセスするので添え字の上限は-1 !!
        rep(i, 1010 - 1) {
            rep(e, 55 - 1) {
                rep(o, 55 - 1) {
                    // i, e, oという取り出し方が存在しないならパス
                    if (!dp[i][e][o])
                        continue;

                    // 次が偶数のとき
                    if ((i + 1) % 2 == 0) {
                        // 次に個数の指定があるとき
                        if (check[i + 1] != -1) {
                            if (e + o == check[i + 1]) {
                                // 次の数を足さないような取り出し方が制約を満たすとき
                                dp[i + 1][e][o] = true;
                            } else if (e + o + 1 == check[i + 1]) {
                                // 次の数を足すような取り出し方が制約を満たすとき
                                dp[i + 1][e + 1][o] = true;
                            }
                        } else {    // 次に個数の指定がないなら取っても取らなくてもよい
                            dp[i + 1][e][o] = true;
                            dp[i + 1][e + 1][o] = true;
                        }
                    } else {    // 次が奇数のとき
                        if (check[i + 1] != -1) {
                            if (e + o == check[i + 1]) {
                                dp[i + 1][e][o] = true;
                            } else if (e + o + 1 == check[i + 1]) {
                                dp[i + 1][e][o + 1] = true;
                            }
                        } else {
                            dp[i + 1][e][o] = true;
                            dp[i + 1][e][o + 1] = true;
                        }
                    }
                }
            }
        }

        return (dp[b][n/2][n/2] == 1) ? "fair" : "unfair";

    }
};

所要時間: -

Overall Accuracy: 43.51%

DPという脳がなかった。