競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

CodeChef April long Challenge 2015 Little Party(LPARTY)

注:この記事はCodeChef終了後に更新しています。
ACできた問題。まさか論理回路系の問題が出るとは。
全体のAC人数が最も少ない問題となっていますが絶対にBWGAMEのほうが難しいと思う、、、

- 問題概要

上手く問題文が読めなかったので上手く訳せているか怪しいです。
パーティーを開きます。今まで開いてきたパーティーは人の組み合わせが良くなかったため全てうまくいきませんでした。
人にはGood moodとBad moodの二つの状態があります。
過去のパーティーの人と状態の組み合わせが与えられるので、良くない人の組み合わせを挙げ、それらを文字列として繋げたときに最も最小の文字数を出力しなさい。
例えばabCとabcが与えられたら、abという組み合わせが悪いことが分かります。
abCabcというのも解になりますがabのほうが文字列は少ないです。

- 解法

論理回路の問題に落とすことができます。
aをAの否定と考えると、入力はn変数の主加法標準形で与えられます。
これを最簡形に直したときの文字の個数がそのまま解になります。
まず入力で文字列がM個与えられます。
Mの最大は1000ですが実際5変数の式の種類数は2^5=32なので無駄な入力がほとんどです。
setを使って必要な入力のみに制限してやりましょう。

計算機で最簡形を求めるときはカルノー図ではなくクワイン・マクラスキー法のほうが実装が楽です。
まず{ab}について考えます。これは入力で{abC},{abc}が与えられたときに{ab}が成り立ちます。
{{abC},{abc}}を{ab}の子とします。
また、{ab},{aB}が成り立つとき、aが成り立ちます。このとき同時に{ac},{aC}も成り立っているはずです。
{{ab},{aB},{ac},{aC}}をaの子とします。この親子関係を全て求めます。
全て求めた後、親が成り立つとき子を使う必要はなくなるので整理します。これで主項が減ります。
主項を減らしましたがまだ最簡形ではありません。

残りの主項から入力の式を満たす最小の組み合わせを上手く見つけなくてはいけません。
主加法標準形の状態数が最大32個なのでbitで管理することが可能です。
一つの方法はmapを使って強引にbitDPです。これは満点もらえません(TLE)。

満点解法はペトリック法を使います。
必須項をあらかじめ求めておき、前述の主項から必須項を省いておきます。
入力で与えられた1つの状態に対し、どの主項が対応するか先に求めておきます。
あとはDFSをします。x&-xで一番下位の1bitを抽出できたりとか__builtin_ctzで一番下位の1bitは何bit目にあるか入手したりとかで高速化しましょう。

DFSでなくバックトラックですね。
5変数の状態は32bitをフルに使うと表せますが、必須項を除いた使うかもしれない主項は状態を少なくとも二つ以上カバーします。
すると引き算をして2(もしくはそれ以上)bitずつ減っていくので結果的にバックトラックの探索を行う深さは16までとなる。という算段です。

計算量はO(2^{n-1})になります。分かりづらくてすみません。

- ソースコード

親子関係のグラフを配列で管理するために構造体を使っています。

#include<algorithm>
#include<utility>
#include<complex>
#include<iostream>
#include<fstream>
#include<sstream>
#include<string>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<list>
using namespace std;
#define reE(i,a,b) for(auto (i)=(a);(i)<=(b);(i)++)
#define rE(i,b) reE(i,0,b)
#define reT(i,a,b) for(auto (i)=(a);(i)<(b);(i)++)
#define rT(i,b) reT(i,0,b)
#define rep(i,a,b) reE(i,a,b);
#define rev(i,a,b) for(auto (i)=(b)-1;(i)>=(a);(i)--)
#define fe(i,b) for (auto &(x):b);
#define itr(i,b) for(auto (i)=(b).begin();(i)!=(b).end();++(i))
#define rti(i,b) for(auto (i)=(b).rbegin();(i)!=(b).rend();++(i))
#define LL long long
#define all(b) (b).begin(),(b).end()
const LL INF = 1 << 20;
const double eps = 1e-8;
const int dir[] = { 0, 1, 0, -1, 0 };
inline int change(string &s,int num){
	int res = 0;
	rT(i, num){
		if ('A' <= s[i] && s[i] <= 'Z')
			res |= (1 << i);
	}
	return res;
}
 
struct node{
	string str;
	list<int> child;
	int size;
	int bit;
	node(){ size = -1; bit = 0; }
	node(string s){ str = s; size = -2; bit = 0; }
};
 
const char alpha[5][3] = { "aA", "bB", "cC", "dD", "eE" };
void make_tree(const int exist,const int n,const int now,vector<node> &tree){
	int b = 0;
	if (tree[now].child.size() == 0){
		b = 1<<change(tree[now].str, n);
		if ((exist&b) != 0){
			tree[now].size = n;
			tree[now].bit = b;
		}
		else{
			tree[now].size = -1;
		}
		return;
	}
	bool f = true;
	for (auto &children : tree[now].child){
		if (tree[children].size == -2)
			make_tree(exist, n, children, tree);
		if (tree[children].size == -1){
			f = false;
		}
		b |= tree[children].bit;
		tree[now].size=tree[children].size - 1;
	}
	if (f == false)b = 0, tree[now].size = -1;
	tree[now].bit = b;
	return;
}
 
void print_bit(int n, int num){
	rT(i, 1<<n)
		if (num&(1 << i))cout << 1; else cout << 0;
}
void delete_child(int now,vector<node> &tree){
	for (auto &c : tree[now].child){
		if (tree[c].size != -1){
			delete_child(c, tree);
			tree[c].size = -1;
		}
	}
}
 
list<int> bit[32];
 
int dfs(int now_bit,vector<node>&tree,int cost,int T){
    if(now_bit==0)return min(cost,T);
    int b=__builtin_ctz(now_bit);
    for(auto &i:bit[b])
        if(cost+tree[i].size<T)
            T=min(T,dfs(now_bit-(now_bit&tree[i].bit),tree,cost+tree[i].size,T));
    return T;
}
 
int main(void){
	int T, M, N;
	scanf("%d",&T);
	while (T--){
	    rT(i,32)bit[i].clear();
		vector<node> tree;
		tree.reserve(1 << 12);
		int EXIST = 0;
		scanf("%d %d",&N,&M);
		string in_str;
		char tmp[6];
		rT(i, M){ scanf("%s",tmp); in_str=tmp;EXIST |= (1 << (change(in_str, N))); }
		tree.push_back(node("-----"));
		map<string,int> uniq;
		rT(i, (int)tree.size()){
			string cp = tree[i].str;
			rT(j, N)
				if (cp[j] == '-'){
				cp[j] = alpha[j][0];
				if (uniq.count(cp) == 0){
					uniq[cp] = (int)tree.size();
					tree.push_back(node(cp));
				}
				tree[i].child.push_back(uniq[cp]);
				cp[j] = alpha[j][1];
				if (uniq.count(cp) == 0){
					uniq[cp] = (int)tree.size();
					tree.push_back(node(cp));
				}
				tree[i].child.push_back(uniq[cp]);
				cp[j] = '-';
			}
		}
 		make_tree(EXIST, N, 0, tree);
		int res=0;
		list<int> index;
		
		rT(i,(int)tree.size()){
		    if(tree[i].size>=0){
		            if(tree[i].size==N){
		                EXIST-=tree[i].bit;
		                res+=N;
		            }
		            else{
		                index.push_back(i);
		                delete_child(i,tree);
		            }
		    }
		}
		//print_bit(N,EXIST);cout<<endl;
		//for(auto &x:tree)if(x.size>=0){cout<<"("<<x.str<<")";print_bit(N,x.bit);cout<<endl;}
		for(auto &i:index){
		    int mask=tree[i].bit&EXIST;
		    for(auto &j:index){
		        if(i!=j){
		            mask=mask&(mask^tree[j].bit);
		        }
		    }
		    if(mask!=0){
		     //cout<<tree[i].str<<endl;
		      EXIST-=(tree[i].bit&EXIST);
		      res+=tree[i].size;
		      tree[i].size=-1;
		    }
		}
		
		//print_bit(N,EXIST);cout<<endl;
        rT(i,32){
		    for(auto &j:index)
			    if(tree[j].size>=0&&((tree[j].bit&(1<<i))&EXIST)!=0)
			        bit[i].push_back(j);
        }
        

		cout << dfs(EXIST,tree,0,10000)+res << endl;
	}
 	return 0;
}