yukicoder : No.2669 Generalized Hitting Set

これ系問題の理解にこんがらがるな…。
https://yukicoder.me/problems/no/2669

問題

1～Nの部分集合S[i]が計M個与えられる。いずれもK個以上の要素を含む。
1～Nの部分集合Tに対し、f(T)は、S[i]との共通要素がK個以上あるものの個数である。
またg(p)は、f(T)がp以上となる最小のTの要素数とする。
g(1)～g(M)を求めよ。

解法

F(i)(T)は、S[i]とTの共通要素数がK以上なら1となる関数とする。
f(i)(T) := S[i]とTの共通要素数がKなら1となる関数とする
うまくメビウス変換して、f(i)(T)に重みを掛けたうえで加減算することでF(i)(T)を求めよう。

この重みは、二項係数の足し引きで求めることができる。

int N,M,K;
ll dp[1<<24];
ll A[25];
int G[303030];


ll comb(ll P_,ll Q_) {
	if(P_<0 || Q_<0 || Q_>P_) return 0;
	ll p=1,q=1;
	Q_=min(Q_,P_-Q_);
	for(int i=1;i<=Q_;i++) p=p*(P_--)/i;
	
	return p;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>s;
		x=0;
		FOR(j,N) if(s[j]=='1') x|=1<<j;
		dp[x]++;
	}
	
	for(i=K;i<=N;i++) {
		A[i]=1;
		for(j=K;j<i;j++) A[i]-=A[j]*comb(i,j);
	}
	
	int mask;
	FOR(i,N) FOR(mask,1<<N) if(mask&(1<<i)) dp[mask^(1<<i)]+=dp[mask];
	FOR(mask,1<<N) dp[mask]*=A[__builtin_popcount(mask)];
	FOR(i,N) FOR(mask,1<<N) if(mask&(1<<i)) dp[mask]+=dp[mask^(1<<i)];
	FOR(i,M+1) G[i]=1<<20;
	
	FOR(mask,1<<N) chmin(G[dp[mask]],__builtin_popcount(mask));
	
	for(i=M-1;i>=0;i--) chmin(G[i],G[i+1]);
	
	for(i=1;i<=M;i++) cout<<G[i]<<endl;
	
	
}

まとめ

この重みをつけてメビウス変換するテク、他にも使えそうだけどまた出てきたときにさっと思い出せる気がしないな。