ICPC2017 国内予選 E 論理式圧縮機
問題
与えられた論理式と常に同じ出力を返すような論理式のうち長さが最小のものを求めよ。
論理式の変数は4つまで、長さは16まで。
解法
長さが15までの論理式を全部生成して、常に出力が同じものがあるかを見る。
なかったら元の論理式を返せばよい。
論理式は入力2^4 = 16通りに対して、それぞれ出力を0, 1に決められるので、
最大で2^16通りが存在しうる。
2^16通りは一意に番号を付けることができて、それを式のキーにするとコードが書きやすい。
ソースコード
不必要な高速化をしてあるので読みにくい。
論理式を生成する際に、これまでに見つかった論理式と出力が常に同じものがあったら、それは使う必要がまったくないので覚えないようにすると結構速くなる。別にやらなくても通った。
unordered_set<string> expr[16]; unordered_map<string, int> exprset; int mns[1 << 16]; int eval(const string &s, int a, int &p){ if(s[p] == '-'){ p++; return !eval(s, a, p); } if(s[p] == '('){ p++; int l = eval(s, a, p); char op = s[p++]; int r = eval(s, a, p); assert(s[p] == ')'); p++; if(op == '*') return l && r; if(op == '^') return l ^ r; assert(0); } char v = s[p++]; if(v == '0' || v == '1') return v == '1'; return a >> (v - 'a') & 1; } int eval(const string &s, int a){ int p = 0; return eval(s, a, p); } int calcset(const string &s){ if(exprset.count(s)) return exprset[s]; int ans = 0; rep(a, 1 << 4) ans |= eval(s, a) << a; return exprset[s] = ans; } int main(){ cin.tie(0); cin.sync_with_stdio(0); rep(i, 1 << 16) mns[i] = 16; for(const auto &p : {"0", "1", "a", "b", "c", "d"}){ expr[1].insert(p); mns[calcset(p)] = 1; } for(int i = 2; i < 16; i++){ for(const auto &j : expr[i - 1]) expr[i].insert("-" + j); for(int j = 1; j < i - 2; j++) for(const auto &k : expr[j]) if(i - j > 3) for(const auto &l : expr[i - j - 3]){ for(const auto &p : {"(" + k + "*" + l + ")", "(" + k + "^" + l + ")"}){ int x = calcset(p); if(mns[x] != 16) continue; expr[i].insert(p); mns[x] = i; } } } for(int i = 1; i < 15; i++) for(const auto &j : expr[i]){ int ans = calcset(j); mns[ans] = min(mns[ans], i); } string s; while(cin >> s, s != "."){ cout << mns[calcset(s)] << endl; } return 0; }