kmjp's blog

競技プログラミング参加記です

AtCoder ARC #125 : E - Snack

このテクは知らなかった。
https://atcoder.jp/contests/arc125/tasks/arc125_e

問題

N種類のお菓子があり、i種類目のお菓子はA[i]個ある。
これらのお菓子をM人の子供に配る。ただし各子供jは、1種類のお菓子をB[j]個以下、合計でC[j]個しか受け取らない。

条件を満たしたうえで、子供に最大何個お菓子を配れるか。

解法

まず計算量は無視して、グラフの最大フロー問題としてこの問題を表現してみる。

  • sourceからお菓子iに容量A[i]の辺を張る
  • お菓子iから子供jにそれぞれ容量C[j]の辺を張る
  • 子供jからsinkに容量B[j]の辺を張る

とすると、このグラフの最大フローは問題の解となる。
ただ、このグラフは辺がO(NM)本になるので、このままでは成り立たない。

そこで、このグラフの最小カットを求めよう。
お菓子のうちA[i]の大きいx個がカットのsource側に来るとする。
その場合、各子供はB[j]*xとC[j]のどちらが大きいかによって、source側とsink側どちら側に属するかが決まる。

あとは、xを総当たりしつつカットの大きさを求め、その最小値を解とすればよい。

int N,M;
ll A[202020],B[202020],C[202020];
vector<int> step[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	ll SA=0;
	FOR(i,N) {
		cin>>A[i];
		SA+=A[i];
	}
	sort(A,A+N);
	reverse(A,A+N);
	
	ll SB=0;
	FOR(i,M) {
		cin>>B[i];
		SB+=B[i];
	}
	ll SC=0;
	FOR(i,M) {
		cin>>C[i];
		if((C[i]+B[i]-1)/B[i]<=N) step[(C[i]+B[i]-1)/B[i]].push_back(i);
	}
	
	ll ret=1LL<<60;
	FOR(i,N+1) {
		FORR(e,step[i]) {
			SC+=C[e];
			SB-=B[e];
		}
		
		ret=min(ret,SA+SC+i*SB);
		SA-=A[i];
	}
	cout<<ret<<endl;
	
	
}

まとめ

勉強になりました。