779-E. Bitwise Formula

2021-03-21 15:44:29 +0800 CST Tags: bitwise

出處：https://codeforces.com/contest/779/problem/E
提交：https://codeforces.com/contest/779/submission/110594588

問題：現在欲宣告 $n\in[1,5000]$ 個位元深度為 $m\in[1,1000]$ 的二進位整數變數，賦值形式可以是單純一個常數，也可以是兩個運算元的 AND、OR、XOR 運算，此時運算元可以是一個我們整題要求的一個固定的未知數 “?"，也可以是先前已經定義好的變數名稱，但就是不會有常數混合在其中。現在我們想知道固定未知數 “?” 應該要是多少才能讓所有宣告變數的總和最小？又應該要是多少才能讓所有宣告變數的總和最大？在這兩個問題之中，如果有多個可行解則找出最小的那一個。

解法：這題的官方作法是要我們直接一個 bit 一個 bit 去試，因為每個 bit 的運算都是獨立的，不受其他 bit 干擾，故總時間就是 $\mathcal O(2nm)$ 仍然在接受範圍內，但這個作法實在不是很聰明，而且 coding 起來頗有難度，換句話說我不知道要怎麼實作，於是我後來採取一個更巧妙的方式。我直接假設欲求未知數 “?” 的每個 bit 都是變數 x，那麼它的補數可表示為 1-x，在任何一個位元運算當中，無論運算元是常數還是變數，最後運算的結果都會是已知的 (deterministic)，也就是說必定是 0、1、x、(1-x) 這四者裡面的其中一種，如此一來我們就可以針對這四者去設計一個「客製化」的運算規則，使得該位元最後的總和必為 ax + b 的形式，其中 a 是求得的整數係數、b 是非負常數。要讓 ax + b 最大，那 x 就必須在 $a>0$ 時為 1；要讓 ax + b 最小，那 x 就必須在 $a<0$ 時為 1；在 $a=0$ 的時候，根據題意，要讓 $x=0$。

實作：上一段有提到所謂的「客製化」運算規則，你可能會想用 2 表示 (1-x)、用 3 表示 x，然後寫一大串 if-else 取代原本的位元運算，只不過這樣子真的就弱掉了，讀者不妨思考看看，如果維持 b'00 表示 0，但是改讓 b'11 表示 1，而 b'01 和 b'10 分別表示 (1-x) 和 (x)，為什麼這樣子就可以讓原本的位元運算原封不動、直接滿足客製化規則呢？可惜這題實測起來速度仍然不夠理想，我猜測是 vector 多次的 push_back 造成的，也許有更好的改進方式。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


#include <bits/stdc++.h>
using namespace std;

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    int n, m; cin >> n >> m;
    vector<short> coefficients;
    map<string, vector<char>> dict;
    for (int i=0; i<n; i++) {
        string a, b, c, d, e;
        cin >> a >> b >> c; assert (b == string(":="));
        if (c[0]=='0' || c[0]=='1') {
            for (int j=0; j<c.length(); j++)
                dict[a].push_back((c[j]-'0') * 0b11); // 0 => 0b00, 1 => 0b11
        } else {
            cin >> d >> e;
            for (int j=0; j<m; j++) {
                int opa = (c[0]=='?') ? 0b10 : dict[c][j]; // x ==> 0b10
                int opb = (e[0]=='?') ? 0b10 : dict[e][j]; // x ==> 0b10
                // we use 0b00 to denote 0, 0b01 to denote (1-x),
                //        0b10 to denote x, 0b11 to denote 1.
                if (d == string("AND")) dict[a].push_back(opa & opb);
                else if (d == string("OR")) dict[a].push_back(opa | opb);
                else if (d == string("XOR")) dict[a].push_back(opa ^ opb);
                else assert (false);
            }
        }
    }
    for (int j=0; j<m; j++) {
        int sum = 0;
        for (auto &kv: dict) {
            if (kv.second[j] == 0b10) sum++; // number of x
            if (kv.second[j] == 0b01) sum--; // number of 1-x
        }
        coefficients.push_back(sum);
    }
    for (int j=0; j<m; j++) cout << 1 - (coefficients[j]>=0);
    cout << '\n';
    for (int j=0; j<m; j++) cout << (coefficients[j]>0);
    cout << '\n';
    return 0;
}

結果： Example image