UTPC 2014 : L - セミ時雨ハッシュ

相変わらずUTPCはキツいグラフ問題が出るなぁ。
http://www.utpc.jp/2014/slides/L.pdf

問題

30変数以下の数式が与えられる。
この数式は異なる2変数の積を多数足したものになっている。
また、同じ2変数の積が複数回登場することはない。
さらに、各変数の登場回数は4回以下である。

各変数に1か-1を割り当てる。
この数式が最小値となる変数の数値の割り当てを求めよ。

解法

部分点は変数が20個なので、2^20通り値を代入して試すだけ。
満点解法はEditorialを見て回答。

互いに掛けられている変数の間に辺を張ったグラフを考える。
各頂点を2色に塗った場合、片方を1、残りに-1を対応させると考えると、異なる色の頂点同士を張った辺が多いほど数式が最小になる。
これは異なる色の頂点同士の最大カットに相当する。

最大カットを求めるためには、各連結成分に置いて極小頂点被覆を求める。
この極小頂点被覆の頂点に対し、それぞれ2色のどちらの色を割り当てるか総当たりする。
残りの頂点は最大カットが最大値になる方の色を選択していけば良い。

変数の登場回数の制限より、極小頂点被覆の頂点数は24以下になるのでなんとか間に合う。

vector<int> E[40];
ll mask[40];
int mat[40][40];

string S;

ll getcov(int cur,ll cmask,vector<int>& V) {
	if(cur==V.size()) return cmask;
	
	ll ret=getcov(cur+1,cmask | (1LL<<V[cur]),V);
	
	FORR(r,E[V[cur]]) if(r<V[cur] && ((cmask&(1LL<<r))==0)) return ret;
	
	ll ret2=getcov(cur+1,cmask,V);
	if(__builtin_popcountll(ret2)<__builtin_popcountll(ret)) ret=ret2;
	return ret;
}


ll pat(vector<int>& V) {
	ll cov=getcov(0,0,V);
	int val[31],mask,i;
	vector<int> C,NC;
	map<int,ll> M;
	FORR(r,V) {
		if(cov & (1LL<<r)) C.push_back(r);
		else NC.push_back(r);
	}
	
	vector<pair<int,int> >NE;
	FOR(i,C.size()) FORR(r,E[C[i]]) if(r<C[i] && (cov&(1LL<<r))) NE.emplace_back(C[i],r);
	
	FOR(mask,1<<C.size()) {
		int tot=0;
		ll p=1;
		FOR(i,C.size()) val[C[i]]=(mask&(1<<i))!=0;
		FORR(r,NE) tot += (val[r.first]!=val[r.second])?1:-1;
		
		FOR(i,NC.size()) {
			int n[2]={};
			FORR(r,E[NC[i]]) n[val[r]]++;
			tot+=abs(n[0]-n[1]);
			if(n[0]==n[1]) p*=2;
		}
		M[tot]+=p;
	}
	
	return M.rbegin()->second;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	for(i=0;i<S.size();i+=2) {
		if(isupper(S[i])) S[i]-='A';
		else S[i]=S[i]-'a'+26;
	}
	for(i=0;i<S.size();i+=4) {
		if(S[i]!=S[i+2]) {
			E[S[i]].push_back(S[i+2]);
			E[S[i+2]].push_back(S[i]);
		}
		mask[S[i]] |= 1LL<<S[i+2];
		mask[S[i+2]] |= 1LL<<S[i];
		mat[S[i]][S[i+2]]=mat[S[i+2]][S[i]]=1;
	}
	FOR(i,30) FOR(x,30) FOR(y,30) mat[x][y] |= mat[x][i]&mat[i][y];
	
	ll ret=1;
	FOR(i,30) if(mask[i] && count(&mat[i][0],&mat[i][i],1)==0) {
		vector<int> V;
		FOR(x,30) if(mat[i][x]) V.push_back(x);
		ret *= pat(V);
	}
	cout<<ret<<endl;
}

まとめ

なんとかUTPC2014は解き終えました。