Codeforces #568 Div2 F. Two Pizzas

問題数が無駄に多いがそこまで難しくなかった回。
http://codeforces.com/contest/1185/problem/F

問題

ピザの具が9種類ある。
ここでN人の人がおり、好きな具として9種類の具の部分集合が与えられる。

また、M種類のピザがある。
各ピザに対し、価格と乗っている具(９種類の具の部分集合)が設定されている。

M種類のピザのうちちょうど2種類を1枚ずつ選ぶことを考える。
両方のピザの具を合わせると、各人の好きな具をすべてカバーする場合、その人はこのピザ２枚組を気に入る。

気にいる人数が最多となる組み合わせのうち、最小価格の物を求めよ。

解法

まず高速ゼータ変換の要領で、具の集合に対し何人の希望を叶えるか計算しよう。
次にピザの組み合わせを総当たりする。
同種のピザを２枚安い分に選ぶ場合と、２種類のピザをそれぞれ最安値で買う場合を考える。
先の高速ゼータ変換の結果があれば、ピザの組合わせを2^18通り程度総当たりしても間に合う。

int N,M;
int num[2525];
int numsum[2525];
vector<pair<int,int>> P[2525];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		x=0;
		cin>>y;
		FOR(j,y) {
			cin>>k;
			x|=1<<(k-1);
		}
		num[x]++;
	}
	FOR(i,M) {
		cin>>r;
		x=0;
		cin>>y;
		FOR(j,y) {
			cin>>k;
			x|=1<<(k-1);
		}
		P[x].push_back({r,i+1});
	}
	FOR(i,1<<9) FOR(j,1<<9) if((i&j)==j) numsum[i]+=num[j];
	
	int ma=-1,co=0;
	pair<int,int> p;
	FOR(i,1<<9) {
		sort(ALL(P[i]));
		if(P[i].size()>=2) {
			if(numsum[i]>ma || (numsum[i]==ma&&P[i][0].first+P[i][1].first<co)) {
				ma=numsum[i];
				co=P[i][0].first+P[i][1].first;
				p={P[i][0].second,P[i][1].second};
			}
		}
	}
	
	FOR(y,1<<9) FOR(x,y) if(P[x].size()&&P[y].size()) {
		r=numsum[x|y];
		j=P[x][0].first+P[y][0].first;
		if(r>ma || (r==ma && j<co)) {
			ma=r;
			co=j;
			p={P[x][0].second,P[y][0].second};
		}
	}
	if(p.first>p.second) swap(p.first,p.second);
	cout<<p.first<<" "<<p.second<<endl;
	
	
}

まとめ

同じピザ２枚は要らなくない？