はまやんはまやんはまやん

hamayanhamayan's blog

短絡評価 [Hokkaido University Programming Contest 2019 Day 1 C]

競技プログラミング

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2019Day1/problems/C

前提知識

解説

https://onlinejudge.u-aizu.ac.jp/services/review.html#HUPC2019Day1/3746462

まずは、与えられた論理式が理解できないと、始まらないので、
?が0,1のどちらかである論理式を処理できるコードを書く。
普通の構文解析より少し難しく、優先度の概念が入っている構文解析を書く必要がある。
仕組みとしては、構文解析の過程で、層を導入することで、処理を行っていく。

string op[2] = { "|", "&" };

int parse(string& s, int& i, int x)
{
    if (x == 2)
    {
        if (s[i] == '(')
        {
            i++;
            int ans = parse(s, i, 0);
            i++;
            return ans;
        }
        else
        {
            int ret = 0;

            if (s[i] == '1') ret = 1;
            i++;

            return ret;
        }
    }
    else
    {
        vector<int> history;
        history.push_back(parse(s, i, x + 1));

        int flag = 0;

        while (op[x].find(s[i]) != string::npos)
        {
            switch (s[i])
            {
            case '|': i++; history.push_back(parse(s, i, x + 1)); flag = 1; break;
            case '&': i++; history.push_back(parse(s, i, x + 1)); flag = 2; break;
            }
        }

        int ans = 0;
        if (flag == 0) ans = history.back();
        else if (flag == 1) {
            ans = 0;
            fore(x, history) ans |= x;
        }
        else if (flag == 2) {
            ans = 1;
            fore(x, history) ans &= x;
        }

        return ans;
    }
}

void test() {
    vector<pair<string, int>> testcase = {
        {"0&1", 0},
        {"1&1", 1},
        {"1&0|1", 1},
        {"1&0|1&0", 0},
        {"1&1&0", 0},
        {"(0|0|0|1)&1&(1&0)", 0}
    };

    fore(p, testcase) {
        int i = 0;
        string s = p.first + "#";
        int actual = parse(s, i, 0);
        int expect = p.second;
        
        if (actual != expect) {
            printf("NG!!! %s = %d : ans %d\n", s.c_str(), actual, expect);
        }
    }
}


//---------------------------------------------------------------------------------------------------
void _main() {
    test();
}

なんとなくテストもして、通れば大体はOK。
次はこれを変形して解いていく。
先頭から解釈していくということであるが、これは構文解析時もそうなので、構文解析内部にロジックを入れていく。

さっきはparse() := 評価結果であったが、parse() := {全体を0にするための最小手数, 全体を1にするための最小手数}として計算していく。
深く考えるべきなのは、OR,ANDの計算である。

ORで全体を1にするための計算では、1|?|?|?とするのが最適であると思いきや、最後のサンプルを見ると、0|1|?|?のようにするのがいいパターンもある。
なので、4つであれば、1|?|?|?, 0|1|?|?, 0|0|1|?, 0|0|0|1のパターンの中で最も手数が少ないものを全体を1とする最小手数として採用すればいい。 全体を0にするには0|0|0|0とするしかないので、総和をとればいい。
ANDについても同様に考えよう。

これで順々に計算していけばいい。

string op[2] = { "|", "&" };

pair<int,int> parse(string& s, int& i, int x)
{
    if (x == 2)
    {
        if (s[i] == '(')
        {
            i++;
            auto ans = parse(s, i, 0);
            i++;
            return ans;
        }
        else
        {
            char c = s[i];
            i++;

            if (c == '1') return { 201010, 0 };
            else if (c == '0') return { 0, 201010 };
            else return { 1, 1 };
        }
    }
    else
    {
        vector<pair<int,int>> history;
        history.push_back(parse(s, i, x + 1));

        int flag = 0;

        while (op[x].find(s[i]) != string::npos)
        {
            switch (s[i])
            {
            case '|': i++; history.push_back(parse(s, i, x + 1)); flag = 1; break;
            case '&': i++; history.push_back(parse(s, i, x + 1)); flag = 2; break;
            }
        }

        if (flag == 0) return history.back();
        
        if (flag == 1) { // or
            int zero = 0;
            int yasui = 0;
            int one = inf;
            fore(p, history) {
                chmin(one, zero + p.second);
                zero += p.first;
            }
            return { zero, one };
        }

        if (flag == 2) { // and
            int zero = inf;
            int yasui = 0;
            int one = 0;
            fore(p, history) {
                chmin(zero, one + p.first);
                one += p.second;
            }
            return { zero, one };
        }
    }
}


string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    S = S + "#";

    int i = 0;
    auto ans = parse(S, i, 0);

    printf("%d %d\n", ans.first, ans.second);
}