AtCoder ABC #144 : E - Gluttony

日曜にずれ込んだのすっかり忘れてた…。
https://atcoder.jp/contests/abc144/tasks/abc144_e

問題

N人の人がN個の料理を食べる。
1人で1個の料理を担当することとし、担当は任意に変えることができる。
各メンバーの消化コストA[i]と、料理の食べにくさB[j]が与えられる。

消化コストxの人が食べにくさyの物を食べるとx*yの時間がかかる。
N人全体が同時に食事を始めるときの完了までの時間、すなわちN人のかかる時間の最大値を最小化したい。
この時、消化コストを負にならない範囲で、整数単位で合計Kまで削減できるとする。

最適な削減順と料理の担当を定めたとき、時間の最小値を求めよ。

解法

解となる時間を二分探索することを考える。
時間が決まっている場合に、それが削減量K以下で達成できるかを判定しよう。
まず料理の担当は一択で、消化コストと食べにくさの積を小さくしたいので、食べにくいものほど消化コストが小さい人が担当することになる。

時間と食べにくさが求まると、各人が許容される消化コストの上限が決まるので、消化コストの初期値がそれを超える場合、その分削減しなければならない。
よってその削減量の総和を求めれべよい。

int N;
ll K;
int A[202020];
int F[202020];

int ok(ll v) {
	ll sum=0;
	int i;
	FOR(i,N) {
		ll ma=v/F[i];
		if(ma<A[i]) sum+=A[i]-ma;
		if(sum>K) return 0;
	}
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	ll S=0;
	FOR(i,N) {
		cin>>A[i];
		S+=A[i];
	}
	FOR(i,N) cin>>F[i];
	
	if(S<=K) return _P("0\n");
	
	sort(A,A+N);
	sort(F,F+N);
	reverse(F,F+N);
	ll mi=1LL<<60;
	for(i=59;i>=0;i--) if(ok(mi-(1LL<<i))) mi-=1LL<<i;
	cout<<mi<<endl;
	
	
}

まとめ

500ptとしては簡単？4問時代のABCのDぐらいかね。