TopCoder SRM 696 Div2 Hard Clicountingd2

こちらは割と楽に解けた。
https://community.topcoder.com/stat?c=problem_statement&pm=14372

問題

N頂点の無向グラフがある。
各頂点間は、以下の何れかである。

• 辺がない
• 辺がある
• 辺があるかないか不明

最後の不明の辺がM個ある場合、辺の組み合わせは2^M通り考えられる。
その全組み合わせにおいて、最大クリークの頂点数の総和を求めよ。

N,Mはいずれも20以下である。

解法

bitdp + 高速ゼータ変換で解く。
以下を求められれば、sum(dp)を答えればいいことがわかる。
dp(mask) := M個の辺のうちmaskに相当する辺が存在する場合の最大クリークの頂点数

Nが20以下と小さいので、クリークを2^N通り列挙しよう。
もしa頂点のクリーク中に辺がない頂点対があるならばそのクリークは存在しえない。
そうでない場合(クリーク中の頂点対は辺が確実にあるか、もしくは不明である)場合、そのクリークを成すのに必要な辺の集合をmaskとするとdp(mask) = aとなる。

仮にdp(mask) = xであるならば、maskをsubsetとして含むmask'に対しdp(mask') = max(dp(mask'),dp(mask))でなければならない。
このような最大値を求める処理は高速ゼータ変換の要領でO(M*2^M)で出来る。

int ma[1<<20];
int id[20][20];

class Clicountingd2 {
	public:
	int count(vector <string> g) {
		int N=g.size();
		int M=0;
		MINUS(id);
		int i,j,x,y,mask;
		FOR(y,N) FOR(x,y) if(g[x][y]=='?') id[x][y]=id[y][x]=M++;
		
		ZERO(ma);
		FOR(mask,1<<N) {
			int yes=1;
			int nm=0;
			FOR(y,N) FOR(x,y) if((mask&(1<<x)) && (mask&(1<<y))) {
				if(g[y][x]=='0') yes=0;
				if(g[y][x]=='?') nm |= 1<<id[y][x];
			}
			if(yes==0) continue;
			ma[nm] = max(ma[nm], __builtin_popcount(mask));
		}
		FOR(i,M) FOR(mask,1<<M) if(mask&(1<<i)) ma[mask] = max(ma[mask], ma[mask^(1<<i)]);
		return accumulate(ma,ma+(1<<M),0);
	}
}

まとめ

これがわからないとDiv1が解けない。