Codeforces #908 : Div1 C. Freedom of Choice

だいぶ苦戦してしまった。
https://codeforces.com/contest/1893/problem/C

問題

multiset Sのanti-beautyとは、S中に含まれる|S|の個数を指す。

今ここでM個のmultisetと、それぞれに対する範囲L[i],R[i]が指定される。
各multisetから、L[i]個以上R[i]個以下の値を抽出し、それらを集めたmultiset Xを考える。

Xのanti-beautyの最小値を求めよ。

解法

X	は、sum(L)からsum(R)の間である。

もしsum(L)～sum(R)のうちに、M個のmultisetに含まれない値があるなら、解は0である。

そうでない場合、sum(L)～sum(R)をそれぞれ総当たりし、|X|を最大何個かき集められるか計算しよう。

int T,M;
int N[202020];
ll L[202020],R[202020],SS[202020];
vector<ll> A[202020],C[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>M;
		ll SL=0,SR=0;
		int NS=0;
		map<ll,vector<pair<int,ll>>> MM;
		FOR(i,M) {
			cin>>N[i]>>L[i]>>R[i];
			NS+=N[i];
			SL+=L[i];
			SR+=R[i];
			SS[i]=0;
			A[i].resize(N[i]);
			C[i].resize(N[i]);
			FOR(j,N[i]) {
				cin>>A[i][j];
			}
			FOR(j,N[i]) {
				cin>>C[i][j];
				SS[i]+=C[i][j];
				MM[A[i][j]].push_back({i,C[i][j]});
			}
		}
		if(SR-SL+1>NS) {
			cout<<0<<endl;
			continue;
		}
		ll mi=1LL<<60;
		for(ll len=SL;len<=SR;len++) {
			if(MM.count(len)==0) {
				mi=0;
				break;
			}
			auto V=MM[len];
			ll sum=SR;
			FORR2(a,b,V) {
				sum-=R[a];
			}
			ll can=0;
			ll must=0;
			ll need=0;
			FORR2(a,b,V) {
				ll oth=min(R[a],SS[a]-b);
				must+=max(0LL,L[a]-(SS[a]-b));
				can+=b-max(0LL,L[a]-(SS[a]-b));
				sum+=oth+max(0LL,L[a]-(SS[a]-b));
			}
			if(sum+can>=len) mi=min(mi,must+max(0LL,len-sum));
			
			
		}
		cout<<mi<<endl;
	}
			
}

まとめ

コーナーケースとかいろいろ怖い問題。