Mister雑記

競プロやります。

AOJ 1619 「弁当作り」

onlinejudge.u-aizu.ac.jp

問題意訳

長さ Mのbit列が N個与えられる。 全体のXORが 0となるような部分集合の、要素数の最大値を求めよ。

制約

  •  1 \leq N, M \leq 500
  •  1 \leq NM \leq 500

考察

あることに気づけるかが鍵となる問題。 それを言ってしまうと終わりなので、まだちゃんと考えてない人は考えてから先に進むことを推奨する。








この問題の肝は「 1 \leq NM \leq 500」という制約で、ここから「 N \leq 23 M \leq 23のいずれかが成立する」ことが分かる。 これの何が嬉しいかというと、毎回 N Mのいずれかでbit全探索ができるのである。

まず N \leq 23のとき。 これは部分集合をbit全探索して 0になるか判定すればいい。 ただし最大で M = 500になるので、bitsetで入力を持つと良いだろう。

次に M \leq 23のとき。 これは dp_b =「全体のXORが bとなるような部分集合の、要素数の最大値」というbitDPで解ける。 N個配列を取るとメモリ不足が怖いので、DPテーブルを使い回すのが良いと思われる。

実装例

onlinejudge.u-aizu.ac.jp

using bits = bitset<500>;
constexpr int INF = 1 << 30;

void solve() {
    /* ----- 入力 ----- */
    int N, M;
    cin >> N >> M;

    int ans = 0;
    if (N <= 23) {
        /* ----- Nが小さいとき ----- */
        vector<bits> B(N);
        for (auto& b : B) cin >> b;

        // 部分集合を全列挙
        for (int b = 0; b < (1 << N); ++b) {
            bits pat(0);
            for (int i = 0; i < N; ++i) {
                if ((b >> i) & 1) pat ^= B[i];
            }

            // xorが0なら要素数で更新
            if (pat.none()) {
                ans = max(ans, __builtin_popcount(b));
            }
        }
    } else {
        /* ----- Mが小さいとき ----- */
        vector<int> dp(1 << M, -INF);
        dp[0] = 0;

        for (int i = 0; i < N; ++i) {
            bits s;
            cin >> s;
            int b = s.to_ulong();  // 入力を整数に変換

            vector<int> ndp = dp;
            for (int p = 0; p < (1 << M); ++p) {
                ndp[b ^ p] = max(ndp[b ^ p], dp[p] + 1);
                // bを使う場合で更新
            }
            swap(dp, ndp);
        }
        ans = dp[0];
    }
    cout << ans << endl;
}

これを投げると5.55sで通るのだが、他の人もその程度の実行時間になるらしい。 50倍かかるからそんなものか。

反省

  • 皆さん気づきましたか?僕は気づきませんでした。
  • bitsetの使い方を復習した。