Codeforces #608 Div2 F. Divide The Students

また面倒な問題。
https://codeforces.com/contest/1271/problem/F

問題

3種類の授業がある。
これらを受ける際、N人の生徒がまず2つのグループに分かれる。
各グループgにおいて、それぞれの授業iを受けられる人数A[g][i]が与えられる。
各生徒は、グループ内の上限の範囲内で、授業を受ける・受けないを選択できるとする。

最終的に、各生徒が3つの授業のどれを受けたか2^3通り考えられる。
1科目以上受けた生徒について、7通りどれに属するか人数が与えられる。
条件を満たす生徒のグループの割り振り及び受講人数が存在するか判定し、存在するなら一例を示せ。

解法

1科目受けた人数と3科目受けた人数から、片方のグループで2科目受けた人数の範囲が定まる。
あとは3つの科目について、それを除く2科目の受講人数のバリエーションを総当たりしよう。

Editorialよりも、下記コメントの方が詳細でわかりやすい。
https://codeforces.com/blog/entry/72164?#comment-564647

int T;
int C[2][3];
int num[8];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		FOR(i,2) cin>>C[i][2]>>C[i][1]>>C[i][0];
		FOR(i,7) cin>>num[7-i];
		
		int XL=max(0,num[7]+num[6]+num[5]+num[4]-C[1][2]);
		int YL=max(0,num[7]+num[6]+num[3]+num[2]-C[1][1]);
		int ZL=max(0,num[7]+num[5]+num[3]+num[1]-C[1][0]);
		int XR=min(num[7]+num[6]+num[5]+num[4],C[0][2]);
		int YR=min(num[7]+num[6]+num[3]+num[2],C[0][1]);
		int ZR=min(num[7]+num[5]+num[3]+num[1],C[0][0]);
		
		int ok=0;
		for(int f6=0;f6<=min(XR,num[6]);f6++) {
			for(int f5=0;f5<=num[5]&&f6+f5<=XR;f5++) {
				for(int f3=0;f3<=num[3]&&f6+f3<=YR && f5+f3<=ZR;f3++) {
					int x=f6+f5;
					int y=f6+f3;
					int z=f5+f3;
					int f7=max(0,min({num[7],XR-x,YR-y,ZR-z}));
					x+=f7;
					y+=f7;
					z+=f7;
					int f4=max(0,min(num[4],XR-x));
					int f2=max(0,min(num[2],YR-y));
					int f1=max(0,min(num[1],ZR-z));
					x+=f4;
					y+=f2;
					z+=f1;
					
					if(x>=XL && x<=XR && y>=YL&&y<=YR&&z>=ZL&&z<=ZR) {
						ok=1;
						cout<<f7<<" "<<f6<<" "<<f5<<" "<<f4<<" "<<f3<<" "<<f2<<" "<<f1<<endl;
						f5=f6=101010;
						break;
						
					}
					
				}
			}
		}
		if(ok==0) {
			cout<<-1<<endl;
		}
	}
}

まとめ

これ本番に詰め切れる気がしないな。