Codeforces ECR #135 : E. Red-Black Pepper

7問回なのに5問目から難易度高め。
https://codeforces.com/contest/1728/problem/E

問題

N皿の食べ物があり、それぞれ唐辛子と胡椒を掛けたときのおいしさA[i],B[i]が与えられる。

以下のクエリM個に答えよ。

• 唐辛子は1パックX皿分、胡椒はY皿分である。これらをちょうど計N皿分になるように買う。
• 各皿に唐辛子か胡椒を振るとき、おいしさの最大値を求めよ。

解法

デフォルトで唐辛子を掛けることにし、胡椒を掛けた場合の差分を考える。
この差分をソートして置き、胡椒を掛けると美味しさがプラスになる範囲で、胡椒を買う量を増やしていこう。
胡椒の買い方はCRTを使い絞っていく。

int N;
ll D[303030];
ll S[303030];
int Q;

ll ext_gcd(ll p,ll q,ll& x, ll& y) { // get px+qy=gcd(p,q)
	if(q==0) return x=1,y=0,p;
	ll g=ext_gcd(q,p%q,y,x);
	y-=p/q*x;
	return g;
}

pair<ll,ll> crt(ll a1,ll mo1,ll a2,ll mo2) { // return (x,y) y=lcm(a1,a2),x%mo1=a1,x%mo2=a2
	ll g,x,y,z;
	g=ext_gcd(mo1,mo2,x,y);
	a1=(a1%mo1+mo1)%mo1;a2=(a2%mo2+mo2)%mo2;
	if(a1%g != a2%g) return pair<ll,ll>(-1,0); // N/A
	__int128_t lcm=mo1*(mo2/g);
	if(lcm<mo1) return pair<ll,ll>(-2,0); // overflow
	
	__int128_t v=a1+((a2-a1)%lcm+lcm)*x%lcm*(mo1/g);
	return make_pair(((v%lcm)+lcm) % lcm,lcm);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N;
	ll sum=0;
	int p=0,nz=0;
	FOR(i,N) {
		cin>>x>>y;
		sum+=x;
		D[i]=y-x;
		if(D[i]>0) p++;
		if(D[i]>=nz) nz++;
	}
	sort(D,D+N);
	reverse(D,D+N);
	FOR(i,N) S[i+1]=S[i]+D[i];
	cin>>Q;
	while(Q--) {
		ll A,B;
		cin>>A>>B;
		ll mb=crt(N%A,A,0,B).first;
		ll g=__gcd(A,B);
		
		if(mb==-1) {
			cout<<-1<<endl;
			continue;
		}
		assert(mb%B==0);
		mb/=B;
		ll add=A/g;
		mb%=add*B;
		if(mb*B>N) {
			cout<<-1<<endl;
			continue;
		}
		ll ma=sum+S[mb*B];
		if(mb*B<p) {
			mb+=(p-mb*B)/B/add*add;
			ma=max(ma,sum+S[mb*B]);
			if((mb+add)*B<=N) {
				ma=max(ma,sum+S[(mb+add)*B]);
			}
		}
		cout<<ma<<endl;
	}
}

まとめ

なんかややこしいだけで余り好きな問題設定ではないな…。