https://www.hackerrank.com/contests/w32/challenges/balls-and-boxes
問題概要
N色のボールがあり、i番目の色のボールはA[i]個ある。
M個の箱があり、j番目の箱にはC[j]個入れられる。
以下のルールで箱にボールを入れる
- 各箱には、各色のボールを多くとも1つだけ入れられる
- i番目のボールをj番目の箱に入れるとB[i][j]個のキャンディーが得られる
- j番目の箱の最大個数をx個超えていた場合は、x^2個のキャンディを支払う
- 全てのボールを入れる必要は無いし、全ての箱を埋める必要も無い
得られるキャンディの個数の最大値は？
前提知識
hamayanhamayan.hatenablog.jp
最小費用流を知らないと確実に解けない
解説
https://www.hackerrank.com/contests/w32/challenges/balls-and-boxes/submissions/code/1301732910
pekempeyさんのコードを読み解きました。
まずフローを使って最大値を求めるので、コストは得点ではなくて損失として考える。
すると、損失を最小化することで得点が最大化できる。
頂点
- ソース(N+M)
- シンク(N+M+1)
- ボール(i)
- 箱(j+N)
それはそうという感じ
辺
(容量,コスト)で表記し、U=3000(最大得点と仮定)しておく
- ソースからボールiへ(A[i], 0)
- ボールiから箱jへ(1, U - B[i][j])
- 箱jからシンクへ(C[j], 0)
これらは直感的に分かる。
これに色々な制約を表現する辺を追加していく
- ボールiからシンクへ(A[i], U)
使われないボールがある可能性があることの表現
- 箱jからシンクへ(1, 2k+1) (k=0...1010)
これが一番むずかしい。
C[i]を越えると差分の二乗だけマイナスされるという部分を表現している。
2k+1というのは損失の増加量で、+1,+3,+5,+7だけ損失が増えるぞという意味。
C[i]以下の場合はコスト0の辺があるので、それが使われて、超えた分だけ、この辺が使われる。
1つだけ超えたら+1されて合計損失1
2つ超えたら+1と+3されて合計損失4
3つ超えたら+1と+3と+5されて合計損失9
という感じでいい感じに損失を調整してくれる。
あとは、これにボールの総数(total)分のフローを流し、最大得点*totalから最小損失を引けば答え
