Codeforces ECR #156 : E. I Wanna be the Team Leader

いうほどリーダー関係する問題か？
https://codeforces.com/contest/1886/problem/E

問題

N人の人がいて、それぞれのストレス耐性はA[i]である。
また、M個の問題があり、それぞれの難易度はB[i]である。

N人で分担してM個の問題を解きたい。
各問題に1人以上が担当する必要がある。
また、1人は1問までしか担当できない。(0問でも良い)

難易度B[i]の問題にK人で当たるとき、各人のストレス耐性はB[i]/K以上でなければならない。
M問を解き切れる問題の割り当てが存在するなら答えよ。

解法

BitDPで解く。
N人をあらかじめソートして置き、「解からx番目以上のストレス耐性の人が残っているなら、最小何人でその問題を解ける」というのをあらかじめ求めておこう。
あとはBitDPの要領で、解き終わった問題に対し残っている人のストレス耐性の下限を保持しよう。

int N,M;
ll A[202020];
int B[22];
int C[22];
pair<int,int> P[202020];
vector<int> R[120];

int mi[21][202020];
pair<int,int> step[21][202020];

int dp[1<<20];
pair<int,int> from[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>A[i];
		P[i]={A[i],i};
	}
	sort(P,P+N);
	
	FOR(i,M) {
		cin>>B[i];
		mi[i][N]=N+1;
		for(j=N-1;j>=0;j--) {
			y=P[j].first;
			x=(B[i]+y-1)/y;
			mi[i][j]=j+x;
			step[i][j]={j,x};
			if(mi[i][j+1]<mi[i][j]) {
				mi[i][j]=mi[i][j+1];
				step[i][j]=step[i][j+1];
			}
		}
	}
	int mask;
	FOR(mask,1<<M) dp[mask]=N+1;
	dp[0]=0;
	FOR(mask,1<<M) if(dp[mask]<N) {
		FOR(i,M) if((mask&(1<<i))==0) {
			if(chmin(dp[mask|(1<<i)],mi[i][dp[mask]])) {
				from[mask|(1<<i)]={mask,dp[mask]};
			}
		}
	}
	
	if(dp[(1<<M)-1]==N+1) {
		cout<<"NO"<<endl;
		return;
	}
	else {
		cout<<"YES"<<endl;
		int cur=dp[(1<<M)-1];
		mask=(1<<M)-1;
		while(cur) {
			x=from[mask].first;
			cur=from[mask].second;
			FOR(i,M) if((mask^x)&(1<<i)) {
				FOR(j,step[i][cur].second) R[i].push_back(P[j+step[i][cur].first].second+1);
			}
			mask=x;
		}
	}
	
	
	FOR(i,M) {
		sort(ALL(R[i]));
		cout<<R[i].size();
		FORR(r,R[i]) cout<<" "<<r;
		cout<<endl;
	}
}

まとめ

難しくはないけど、復元があるのがめんどいな。