AOJ 1620 論理式圧縮機

解法

4変数に0/1を代入した時の評価結果は16bitで保持できる.
よって, 与えられたBNFから生成されうる文字列の内, 短いものから順に全て列挙していっても間に合う.
最短でない論理式から最短の論理式は生成され得ないのでそこの枝刈りは必要.

ソースコード

AIZU ONLINE JUDGE: Code Review

#include "bits/stdc++.h"

using namespace std;

// <expr> := 0 | 1 | a | b | c | d | -<expr> |  (<expr> ^ <expr>) | (<expr> * <expr>)
string s;
int pos;

// (a,b,c,d) を含まない <expr> に対する値を計算
bool expr()
{
    if (s[pos] == '0')
    {
        pos++;
        return 0;
    }
    if (s[pos] == '1')
    {
        pos++;
        return 1;
    }
    if (s[pos] == '-')
    {
        pos++;
        return !expr();
    }
    assert(s[pos] == '(');
    pos++; // (
    bool x = expr();
    assert(s[pos] == '^' || s[pos] == '*');
    bool f = (s[pos] == '^');
    pos++; // ^ or *
    bool y = expr();
    pos++; // )
    if (f)
        return x ^ y;
    else
        return x & y;
}

// str を 16bit 整数に変換
int calc(const string &str)
{
    vector<vector<int>> ps(4); // a,b,c,d
    int n = str.size();
    for (int i = 0; i < n; i++)
    {
        if (str[i] == 'a')
            ps[0].push_back(i);
        else if (str[i] == 'b')
            ps[1].push_back(i);
        else if (str[i] == 'c')
            ps[2].push_back(i);
        else if (str[i] == 'd')
            ps[3].push_back(i);
    }
    int mask = 0;
    for (int i = 0; i < 16; i++)
    {
        pos = 0;
        s = str;
        for (int j = 0; j < 4; j++)
        {
            // "abcd"[j] は (i>>j)&1 にする
            char c = '0' + ((i >> j) & 1);
            for (auto index : ps[j])
            {
                s[index] = c;
            }
        }
        if (expr())
            mask |= (1 << i);
    }
    return mask;
}

// 整数値->最短論理式長
map<int, int> ret;

// ret を構築
void construct()
{
    set<string> ex = {"0", "1", "a", "b", "c", "d"};
    for (auto str : ex)
    {
        int val = calc(str);
        // cout << val << endl;
        ret[val] = 1;
    }
    // i 文字の論理式を作る
    for (int i = 2; i <= 16; i++)
    {
        set<string> tmp;
        for (const auto &ss : ex)
        {
            string ns = "-" + ss;
            if ((int)ns.size() == i)
            {
                int val = calc(ns);
                if (ret.find(val) == ret.end())
                {
                    ret[val] = i;
                    tmp.insert(ns);
                }
            }
            for (const auto &tt : ex)
            {
                ns = "(" + ss + "^" + tt + ")";
                if ((int)ns.size() == i)
                {
                    int val = calc(ns);
                    if (ret.find(val) == ret.end())
                    {
                        ret[val] = i;
                        tmp.insert(ns);
                    }
                }
                ns = "(" + ss + "*" + tt + ")";
                if ((int)ns.size() == i)
                {
                    int val = calc(ns);
                    if (ret.find(val) == ret.end())
                    {
                        ret[val] = i;
                        tmp.insert(ns);
                    }
                }
            }
        }
        // cerr << i << endl;
        for (const auto &str : tmp)
        {
            // cout << str << endl;
            ex.insert(str);
        }
    }
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    construct();
    string str;
    while (cin >> str, str != ".")
    {
        cout << ret[calc(str)] << endl;
    }
}

感想

書いてて楽しかった.
手元で10秒弱かかってTLE覚悟で投げたら0.94sで通った. ジャッジ速すぎ.