pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

ICPC 2017 国内予選E: 論理式圧縮機

解法

DP。dp[i]=出力が i となるような論理式の最小の長さとする。DPのインデックスはf(0000),f(0001),f(0010),...,f(1111)の出力結果を16ビットにまとめたものである。

遷移にループが生じるため、最短経路的なDPを行う必要がある。bellman-ford的な手法により、2^32回近いループを回せば計算できる。本番中では実際にそのようにして計算したが、2分近い計算時間が必要になるという問題点がある。対処は簡単で、16以上の長さのものからは遷移しないようにすれば数秒で計算が終わる。

(本番中に書いたコードとは異なります。テストケースが手元にないため、正しい解を返すかどうかは未検証です)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>

bool upd(int &x, int y) {
	if (x > y) {
		x = y;
		return true;
	}
	return false;
}

int eval(std::string s, int x) {
	int k = 0;
	std::function<int()> f = [&]() -> int {
		if (s[k] == '0') { k++; return 0; }
		if (s[k] == '1') { k++; return 1; }
		if (s[k] == 'a') { k++; return x >> 0 & 1; }
		if (s[k] == 'b') { k++; return x >> 1 & 1; }
		if (s[k] == 'c') { k++; return x >> 2 & 1; }
		if (s[k] == 'd') { k++; return x >> 3 & 1; }
		if (s[k] == '-') { k++; return 1 ^ f(); }
		k++;
		int x = f();
		char op = s[k];
		k++;
		int y = f();
		k++;
		return op == '^' ? (x ^ y) : (x & y);
	};
	return f();
}

int main() {
	std::vector<int> dp(1 << 16, 16);
	dp[0] = 1;
	dp[(1 << 16) - 1] = 1;
	for (int i = 0; i < 4; i++) {
		int tmp = 0;
		for (int j = 0; j < 1 << 4; j++) {
			if (j >> i & 1) {
				tmp |= 1 << j;
			}
		}
		dp[tmp] = 1;
	}

	while (true) {
		bool ch = false;
		for (int i = 0; i < 1 << 16; i++) {
			if (dp[i] >= 16) continue;
			ch |= upd(dp[0xffff ^ i], dp[i] + 1);
			for (int j = 0; j < 1 << 16; j++) {
				ch |= upd(dp[i & j], dp[i] + dp[j] + 3);
				ch |= upd(dp[i ^ j], dp[i] + dp[j] + 3);
			}
		}
		if (!ch) break;
	}

	while (true) {
		std::string s;
		std::cin >> s;
		if (s == ".") break;
		int mask = 0;
		for (int i = 0; i < 1 << 4; i++) {
			mask |= eval(s, i) << i;
		}
		std::cout << dp[mask] << std::endl;
	}
}