TopCoder SRM 694 Div1 Medium DistinguishableSetDiv1、Div2 Medium DistinguishableSetDiv2

なんとか思いつけて良かった。
https://community.topcoder.com/stat?c=problem_statement&pm=14306
https://community.topcoder.com/stat?c=problem_statement&pm=14305

問題

N人にM個の質問をするもとを考える。
i番目の人にのj問目への回答A[i][j]が与えられる。
M個のうちのsubsetを質問したとき、N人が区別可能かどうか(どの2名も、最低1問は異なる回答を返すか)を考える。
subsetの取り方2^M通りのうち、そのようなものの数を答えよ。

解法

Div2 MediumはMが小さいので、実際にsubsetを2^M通り取ればよい。
この手法はO(N*M*2^M)～O(N^2*M*2^M)程度かかるので、Div2は通るがDiv1はTLEする。

そこで別の手段を考えよう。
ある２人x,yを区別するには、２人が異なる回答を返す質問を少なくとも1問含まなければならない。
逆に考えると、2人が同じ回答を返す質問だけ集めても２人を区別できない。
そのような質問をbitmaskで表現したものをf(x,y)としよう。(その問題では2人を区別できない場合、すなわちA[x][i]==A[y][i]の場合、i bit目は1)
f(x,y)のsubsetもやはり２人を区別できないので条件を満たさない。

x,yを総当たりし、f(x,y)を列挙して条件を満たさない質問群としてマークしよう。
さらに高速ゼータ変換の要領で、f(x,y)のsubsetも条件を満たさない質問群としてマークする。
あとは2^M通りのbitmaskのうち、マークされないものの数を答えればよい。

int ng[1<<20];

class DistinguishableSetDiv1 {
	public:
	int count(vector <string> A) {
		int N=A.size();
		int M=A[0].size();
		
		ZERO(ng);
		
		int y,x,mask,i;
		FOR(y,N) FOR(x,y) {
			mask=0;
			FOR(i,M) mask |= (A[x][i]==A[y][i])<<i;
			ng[mask]=1;
		}
		
		FOR(i,M) FOR(mask,1<<M) ng[mask] |= ng[mask | (1<<i)];
		
		return (1<<M)-std::count(&ng[0],ng+(1<<M),1);
		
	}
}

まとめ

コードにするとすごい短いね。