Codeforces Round #134 (Div. 1) C : Formurosa

問題概要

bool演算を考える。ビット演算で定義されたm変数関数f(x1,...,xm)がある。n個の変数X1,..,XN(2<=N<10^6)がある。ただし、どれか二つは異なる値を持つことが分かっている。fを利用して全ての変数X1,...,XNの値を決定することができるかどうか判定する問題。

解法

まず、f(0,0,...,0)とf(1,1,...,1)の値が異なるなら当然YESになる。
今、fが恒真(or恒偽)関数だとする。この場合は当然NOになる。そうでないとき、適当に2個変数を選んでfに適当に放り込むとそのうちf(0,...,0)と違う値を得ることができる。これにより、どの2個の変数が互いに異なるか求めることができる。で、2個の変数が違うことが分かっているとき片方の値を決定できれば残りの変数を全て求めることができる。逆に、分からない変数を増やすメリットは無いので、結局N=2の場合を解けば十分ということになる。
で、N=2の場合を考える。狙った変数の値(or狙った変数の否定)をとった値がfから取り出せればよい。これは構文解析で計算結果を(trueにできるか、falseにできるか、狙った変数(orその否定)にできるか)の3種類考えて計算すればよい。
あと、構文解析の部分はスタックオーバーフローしなかった。CodeForcesのg++はスタック領域大きいらしい。

acceptされたコード

#include <cstdio>
#include <cstring>
using namespace std;

struct Result {
	bool T, F, X;

	Result(){}
	Result(bool T, bool F, bool X):
		T(T), F(F), X(X)
	{}

};


const int MAX_L = int(1e6);

int N, L, p;
char original[MAX_L + 1];
char line[MAX_L + 1];

void init() {
	scanf("%d", &N);
	scanf(" %s ", original);
	L = strlen(original);
}

Result operator& (const Result& lhs, const Result& rhs) {
	Result r(false, false, false);
	if (lhs.T && rhs.T) {
		r.T = true;
	}
	if (lhs.F || rhs.F || (lhs.X && rhs.X)) {
		r.F = true;
	}
	if ((lhs.T && rhs.X) || (lhs.X  && rhs.T) || (lhs.X && rhs.X)) {
		r.X = true;
	}
	return r;
}

Result operator| (const Result& lhs, const Result& rhs) {
	Result r(false, false, false);
	if (lhs.T || rhs.T || (lhs.X && rhs.X)) {
		r.T = true;
	}
	if (lhs.F && rhs.F) {
		r.F = true;
	}
	if ((lhs.F && rhs.X) || (lhs.X && rhs.F) || (lhs.X && rhs.X)) {
		r.X = true;
	}
	return r;
}

Result operator^ (const Result& lhs, const Result& rhs) {
	Result r(false, false, false);
	if ((lhs.T && rhs.F) || (lhs.F && rhs.T) || (lhs.X && rhs.X)) {
		r.T = true;
	}
	if ((lhs.T && rhs.T) || (lhs.F && rhs.F) || (lhs.X && rhs.X)) {
		r.F = true;
	}
	if (((lhs.T || lhs.F) && rhs.X) || (lhs.X && (rhs.T || rhs.F))) {
		r.X = true;
	}
	return r;
}

Result parse() {
	Result r;
	if (line[p] == '(') {
		++p;
		Result lhs = parse();
		char op = line[p++];
		Result rhs = parse();
		++p;
		if (op == '&') {
			r = lhs & rhs;
		}
		else if (op == '|') {
			r = lhs | rhs;
		}
		else {
			r = lhs ^ rhs;
		}
	}
	else if (line[p] == '0') {
		++p;
		r = Result(false, true, false);
	}
	else if (line[p] == '1') {
		++p;
		r = Result(true, false, false);
	}
	else if (line[p] == '?') {
		++p;
		r = Result(false, false, true);
	}
	return r;
}

bool preSolve() {
	for (int i = 0; i < L; ++i) {
		line[i] = original[i];
		if (line[i] == '?') {
			line[i] = '0';
		}
	}
	p = 0;
	bool t0 = parse().T;

	for (int i = 0; i < L; ++i) {
		line[i] = original[i];
		if (line[i] == '?') {
			line[i] = '1';
		}
	}
	p = 0;
	bool t1 = parse().T;

	return t0 != t1;
}

bool solve() {
	if (preSolve()) {
		return true;
	}

	for (int i = 0; i < L; ++i) {
		line[i] = original[i];
	}

	p = 0;
	Result r = parse();
	return r.X;
}

int main() {
	init();
	puts(solve() ? "YES" : "NO");

	return 0;
}