AOJ1620 Boolean Expression Compressor

去年はちんぷんかんぷんでしたが。
解けるようになるもんですね。

感想

えー、ごり押しです。

文字列の長さが16までなので全部見てみます。

すべての文字列に対してabcdがそれぞれ0,1の場合、つまり16通りの結果を調べてメモ化。
同じ結果の出るものについては最小の文字列長を記憶します。

さて、本番なら二分探索してしまえばいいですが、今回は8秒以内に納めないといけないので少し高速化します。



まず調べる文字列長は15までにします(16文字の論理式は実際に求めるやるか15字以内のどれかしか答えになり得ない)。
また'-'の記号は二つ以上並べるのは無駄なのでこれもやめます。

また、文字列をいじくったり文字列でdfsするとき、なるべく文字列のインスタンスを作らない方が早くなりますね(グローバルにおいて使いまわす等)。



ということでなんとか1.3秒ほどに納めることができました。

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int WWW = 0;WWW < (n);WWW++)cerr << v[WWW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

set<string> s;
int dp[1 << 16];
int place;
char sstr[20];

int dfs2(){
	if(sstr[place] == '-'){
		place++;
		return 1 - dfs2();
	}
	else if(sstr[place] == '('){
		place++;
		int a = dfs2();
		char c = sstr[place];
		place++;
		int b = dfs2();
		place++;
		if(c == '^')return a ^ b;
		else return a & b;
	}
	else{
		return sstr[place++] - '0';
	}
}

int f(){
	place = 0;
	return dfs2();
}

int investigate(string str){
	int ret = 0;
	REP(i,(1<<4)){
		REP(j,str.size()){
			if(str[j] >= 'a' && str[j] <= 'd'){
				sstr[j] = (char)('0' + ((i & (1 << (str[j] - 'a')))>0));
			}
			else{
				sstr[j] = str[j];
			}
		}
		ret |= (f() << i);
	}
	return dp[ret] = min(dp[ret],(int)str.size());
}


void check(string str){
	int cou = 0;
	REP(i,str.size()){
		if(str[i] == 'X')cou++;
	}
	int num = 1;
	REP(i,cou)num *= 6;
	REP(i,num){
		string now = "";
		int tmp = i;
		REP(j,str.size()){
			if(str[j] == 'X'){
				int seica = tmp % 6;
				if(seica < 4){
					now += (char)('a' + seica);
				}
				else{
					now += (char)('0' + (seica - 4));
				}
				tmp /= 6;
			}
			else{
				now += str[j];
			}
		}
		investigate(now);
	}
}

void dfs(string str){
	if(str.size() > 15 || s.count(str))return;
	s.insert(str);
	check(str);
	REP(i,str.size()){
		if(str[i] == 'X'){
			dfs(str.substr(0,max(0LL,i)) + "(X*X)" + str.substr(i+1));
			dfs(str.substr(0,max(0LL,i)) + "(X^X)" + str.substr(i+1));
			if(!(i > 0 && str[i-1] == '-'))dfs(str.substr(0,max(0LL,i)) + "-X" + str.substr(i+1));
		}
	}
}	
	

int main(){
	REP(i,1<<16)dp[i] = INF;
	dfs("X");
	string str;
	while(cin >> str,str[0] != '.'){
		cout << investigate(str) << endl;
	}
	return 0;
}

一回全部'X'で作ってから割り振るということをしています。これがいいのか悪いのかはわからないね。書きやすいと私は思ったけど。