Codeforces #908 : Div1 D. Colorful Constructive

結構コード長いな。
https://codeforces.com/contest/1893/problem/D

問題

N個のキューブがあり、それぞれの色が与えられる。
これらをM個の入れ物に入れたい。
各入れ物のサイズS[i]と、1つの入れ物に同色のキューブを2個以上入れる場合、許容される距離の下限D[i]が与えられる。
条件を満たすキューブの入れ方を構築せよ。

解法

サイズS、下限Dの入れ物があったとき、同じ色のキューブはS%D色は(S/D+1)個、残りはS/D個だけ入れられる。
同色の多いキューブから、まず貪欲に個数を当てはめる。
あとは、入れ物内の並べ方を、同色がD個以上離れるように配置していく。

int T,N,M;
int A[202020],C[202020],S[202020],D[202020];
multiset<int> num[202020];
vector<pair<int,int>> cand[202020];
vector<vector<int>> ret[202020];
vector<int> sz[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N+2) {
			C[i]=0;
		}
		FOR(i,N) {
			cin>>A[i];
			C[A[i]]++;
		}
		vector<pair<int,int>> cand;
		FOR(i,N+1) if(C[i]) cand.push_back({C[i],i});
		FOR(i,M) {
			cin>>S[i];
		}
		priority_queue<pair<int,pair<int,int>>> Q;
		FOR(i,M) {
			cin>>D[i];
			ret[i].clear();
			sz[i].clear();
			x=S[i];
			while(x) {
				y=min(D[i],x);
				x-=y;
				ret[i].push_back({});
				sz[i].push_back(y);
				Q.push({y,{i,(int)sz[i].size()-1}});
			}
		}
		sort(ALL(cand));
		reverse(ALL(cand));
		int ng=0;
		FORR2(c,i,cand) {
			queue<pair<int,int>> PQ;
			while(Q.size()&&c) {
				auto p=Q.top().second;
				Q.pop();
				ret[p.first][p.second].push_back(i);
				sz[p.first][p.second]--;
				if(sz[p.first][p.second]) PQ.push(p);
				c--;
			}
			if(c) {
				ng=1;
				break;
			}
			while(PQ.size()) {
				auto p=PQ.front();
				PQ.pop();
				Q.push({sz[p.first][p.second],p});
			}
		}
		if(ng) {
			cout<<"-1"<<endl;
			continue;
		}
		FOR(i,M) {
			reverse(ALL(ret[i]));
			sort(ALL(ret[i][0]));
			for(j=1;j<ret[i].size();j++) {
				map<int,int> pre;
				FOR(k,ret[i][j-1].size()) pre[ret[i][j-1][k]]=k;
				vector<int> tar(D[i],-1);
				FORR(r,ret[i][j]) {
					if(pre.count(r)) {
						tar[pre[r]]=r;
						r=-1;
					}
				}
				k=0;
				FORR(r,ret[i][j]) if(r!=-1) {
					while(tar[k]!=-1) k++;
					tar[k]=r;
				}
				ret[i][j]=tar;
			}
			reverse(ALL(ret[i]));
			FORR(R,ret[i]) FORR(r,R) cout<<r<<" ";
			cout<<endl;
		}
		
	}
}

まとめ

シンプルな問題設定ながら、地味にやることが多い。