Codeforces #947 : F. Set

こっちはコード短いな。
https://codeforces.com/contest/1975/problem/F

問題

整数集合Tに対し、f(T)とはi∈Tに対する2^iの総和とする。

整数Nに対し、(2^N-1)個の集合V[i]が与えられる。
以下を満たすSを列挙せよ。

• Sは{0,...,N-1}の空でない部分集合
• {0,...,N-1}の空でないあらゆる部分集合Tに対し、|S∩T|∈V[F(T)]である。

解法

畳み込みの要領で、上のbitからVを更新していくと、最終的にSとして残せる値がわかる。

int N;
int V[1<<20];

void dfs(int cur,int d) {
	if(d==0) {
		return;
	}
	int x=1<<(d-1),i;
	FOR(i,x) {
		int a=V[cur+i];
		int b=V[cur+i+x];
		V[cur+i]=a&b;
		V[cur+x+i]=a&(b>>1);
	}
	dfs(cur,d-1);
	dfs(cur+x,d-1);
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	V[0]=1;
	for(i=1;i<=(1<<N)-1;i++) cin>>V[i];
	
	dfs(0,N);
	
	int num=0;
	FOR(i,1<<N) if(V[i]&1) num++;
	cout<<num<<"\n";
	FOR(i,1<<N) if(V[i]&1) cout<<i<<"\n";
}

まとめ

本番かなり時間を掛けて解いてるな…コードは短いけど。