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'で作ってから割り振るということをしています。これがいいのか悪いのかはわからないね。書きやすいと私は思ったけど。