東京大学プログラミングコンテスト2011: I. ビット演算

,

solution

bit数$K = \log \max x_i$に対し$\mathrm{dp} : (K+1) \times 2^N \to \mathrm{String}$なDP。$O(K2^N)$。

それぞれの桁ごとに作ってbit和を取ればよい。 左右shiftや除算がないので、上位の桁の不一致を下位の桁の不一致へは運べない。 例えば$f(0) = 0; \; f(2) = 1$であるような関数は書けない。 よって下から$k$桁目については、$0, 1, \dots, k - 1$桁目を((x*8)&16)などとして取り出しこれらから構成できるものが全てである。 これは簡単なDPで求まる。

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
using namespace std;
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

void check(int n, vector<uint32_t> const & x, vector<uint32_t> const & y) {
    auto distinguishable = vectors(n, n, bool());
    REP (k, 8) {
        REP (j, n) REP (i, j) if (i != j) {
            if ((x[i] & (1 << k)) != (x[j] & (1 << k))) {
                distinguishable[i][j] = true;
            }
            if ((y[i] & (1 << k)) != (y[j] & (1 << k))) {
                assert (distinguishable[i][j]);
            }
        }
    }
}

uint8_t kth_column(vector<uint32_t> const & x, int k) {
    int n = x.size();
    assert (n <= 8);
    uint8_t acc = 0;
    REP (i, n) {
        if (x[i] & (1 << k)) {
            acc |= 1 << i;
        }
    }
    return acc;
}

int main() {
    // input
    int n; cin >> n;
    vector<uint32_t> x(n), y(n);
    REP (i, n) cin >> x[i] >> y[i];
    // solve
    check(n, x, y);
    string result = "0";
    vector<string> memo(1 << n);
    memo[0] = "0";
    memo[(1 << n) - 1] = "1";
    REP (k, 8) {
        // prepare a queue
        queue<uint8_t> que;
        auto push = [&](uint8_t a, string const & s) {
            if (memo[a].empty()) {
                que.push(a);
                memo[a] = s;
            }
        };
        { // add a new primitive
            ostringstream oss;
            oss << "(x&" << (1 << k) << ")";
            push(kth_column(x, k), oss.str());
        }
        // breath first search
        while (not que.empty()) {
            uint8_t a = que.front(); que.pop();
            string s = memo[a];
            {
                ostringstream oss;
                oss << "((~" << s << ")&" << (1 << k) << ")";
                push((~ a) & ((1 << n) - 1), oss.str());
            }
            REP (b, 1 << n) if (not memo[b].empty()) {
                string t = memo[b];
                push(a & b, "(" + s + "&" + t + ")");
                push(a | b, "(" + s + "|" + t + ")");
                push(a ^ b, "(" + s + "^" + t + ")");
            }
        }
        // add to the result
        assert (not memo[kth_column(y, k)].empty());
        result = "(" + result + "|" + memo[kth_column(y, k)] + ")";
        // lshift old items
        REP (a, 1 << n) if (not memo[a].empty()) {
            memo[a] = "(" + memo[a] + "*2)";
        }
    }
    // output
    cout << result << endl;
    return 0;
}