AtCoder ABC #332 : G - Not Too Many Balls

これは全く思い浮かばなかった。
https://atcoder.jp/contests/abc332/tasks/abc332_g

問題

N種類のボールがあり、i番目の種類のボールはA[i]個ある。
M個の箱があり、j番目の箱には合計B[j]個のボールを入れられる。
また、同じ種類のボールはi*j個入れることができる。

条件を満たす範囲で、ボールを最大何個箱に入れることができるか。

解法

source→(ボールの種類別のN点)→(箱別のM点)→sink
と有向辺を張ると、これは最大フロー問題に落とすことができるが、辺の数がO(N*M)あり普通の最大フローのアルゴリズムでは間に合わない。
そこで最小カットを求めることを考える。

source→(ボールの種類別のN点)の部分で、仮にカットとなる辺に対し、対応するボール種類番号の総和がSだとする。
その場合、箱別のM点に対し、その点に関する最小カットはmin((N*(N+1)/2-S)*j,B[j])となる。
よってその総和を取れば、(ボールの種類別のN点)→(箱別のM点)→sinkの部分の最小カットを求めることができる。

そこで、source→(ボールの種類別のN点)の部分で、カットとなる辺に対応するボール種類番号の総和に対し、A[i]の総和の最小値を求める。
各総和に対し、上述のmin((N*(N+1)/2-S)*j,B[j])を求めることで最小カットを求めよう。

int N,M;
ll SA;
ll dp[505*505];
ll P[505*505];
ll Q[505*505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,(N+2)*(N+2)) dp[i]=1LL<<60;
	dp[0]=0;
	
	FOR(i,N) {
		ll A;
		cin>>A;
		for(j=(i+2)*(i+3)/2;j>=0;j--) dp[j+i+1]=min(dp[j+i+1],dp[j]+A);
	}
	
	FOR(i,M) {
		ll B;
		cin>>B;
		ll mi=B/(i+1);
		P[0]+=i+1;
		if(mi<=505*500) {
			P[mi+1]-=i+1;
			Q[mi+1]+=B;
		}
	}
	
	ll ret=1LL<<60;
	
	FOR(i,N*(N+1)/2+1) {
		if(i) {
			P[i]+=P[i-1];
			Q[i]+=Q[i-1];
		}
		ret=min(ret,dp[N*(N+1)/2-i]+P[i]*i+Q[i]);
	}
	cout<<ret<<endl;
}

まとめ

最小カットを求める代わりに最大フローを求める問題はよくあるけど、逆は珍しい。