Codeforces #860 : Div2 F. Gifts from Grandfather Ahmed

これも問題設定がちょっとややこしいな。
https://codeforces.com/contest/1798/problem/F

問題

計N+1人の学生が、K個のクラスに属している。
ここで(N+1)個の箱を準備し、各クラスにクラスの人数分の箱を配ることを考える。
各箱にはプレゼントが入っている。

うちN個はプレゼントの個数が確定しており、1個は未確定である。
残り1個の箱のプレゼント数を適切に設定し、各クラスに配られた箱のプレゼントの総数が、クラスの学生の人数の倍数であるようにせよ。

解法

2N-1個の整数があるとき、うちN個を取るとNの倍数になるような組み合わせが必ずある。
そこで、クラスを人数の少ない順に処理しよう。
最後のクラス以外では、クラスの人数nより箱の数が2n-1以上あるので、必ず可能な組み合わせがある。
これは愚直にDPを復元すればよい。

最後のクラスでは、未確定の箱のプレゼントを設定して、クラスの人数で割り切れるようにすればよい。

int N,K;
int A[202],S[202],vis[203];

int from[202][202][202];
vector<int> ret[202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i];
	vector<pair<int,int>> cand;
	FOR(i,K) {
		cin>>S[i];
		cand.push_back({S[i],i});
	}
	sort(ALL(cand));
	FOR(i,K-1) {
		
		int num=cand[i].first;
		FOR(x,202) FOR(y,num+1) FOR(k,num+1) from[x][y][k]=-1;
		from[0][0][0]=0;
		FOR(j,N) {
			if(vis[j]==1) {
				FOR(x,num+1) FOR(y,num+1) {
					if(from[j][x][y]!=-1) from[j+1][x][y]=0;
				}
			}
			else {
				FOR(x,num+1) FOR(y,num+1) if(from[j][x][y]!=-1) {
					from[j+1][x][y]=0;
					from[j+1][x+1][(y+A[j])%num]=1;
				}
			}
			
		}
		vector<int> R;
		int cur=num,pos=0;
		for(j=N;j>0;j--) {
			if(from[j][cur][pos]==1) {
				ret[cand[i].second].push_back(A[j-1]);
				vis[j-1]=1;
				cur--;
				pos=((pos-A[j-1])%num+num)%num;
			}
		}
	}
	x=0;
	FOR(i,N) if(vis[i]==0) {
		ret[cand[K-1].second].push_back(A[i]);
		x+=A[i];
	}
	x=cand[K-1].first-x%cand[K-1].first;
	ret[cand[K-1].second].push_back(x);
	cout<<x<<endl;
	FOR(i,K) {
		FORR(a,ret[i]) cout<<a<<" ";
		cout<<endl;
	}
	
}

まとめ

この定理知らなかったな。