ARC 031 D - 買い物上手

• 問題
• AC

得られた経験値/使ったお金の最大値を二分探索で探す。

買うアイテムを表すベクトルを$x \in \{0, 1\}^M$とする。$\lambda > 0$が与えられたとき、得られた経験値/使ったお金が$\lambda$以上であることは

$\frac{S_1x(A_{1,1}) x(A_{1,2})... x(A_{1,k_1}) + ... + S_Nx(A_{N,1})x(A_{N,2})... x(A_{N,k_N})}{T_1x(1) + ... + T_Mx(M)} \ge \lambda$

と表され、これは$x \neq 0$という条件下では

$-\lambda T_1x(1)- ... -\lambda T_Mx(M) \\ + S_1x(A_{1,1}) x(A_{1,2})... x(A_{1,k_1}) + ... + S_Nx(A_{N,1})x(A_{N,2})...x(A_{N,k_N}) \ge 0$

と同値である。したがって、大ざっぱに言えば、左辺が$0$以上になるような最大の$\lambda$を二分探索で求めればよい。

（ただ、後者の不等式は$x = 0$、つまりアイテムをひとつも買わないケースで常に成立してしまうため、これを除かなければならない。$x=0$ の場合に不等式が成り立たないようにするためには、double floatの計算誤差よりは大きいが問題の許容誤差よりは小さい数$\epsilon$（たとえば$10^{-7}$）を設定して

$-\lambda T_1x(1)- ... -\lambda T_Mx(M) \\ + S_1x(A_{1,1}) x(A_{1,2})... x(A_{1,k_1}) + ... + S_Nx(A_{N,1})x(A_{N,2})...x(A_{N,k_N}) \ge \epsilon$

とすればよい。）

さて、$\lambda$を決めた時に左辺の最小値は最小カットで求まる。以下はyosupoさんのフレームワークにしたがって考える。

項$- \lambda T_i x(i)$は次のように解釈する:

• 物$\alpha_i$を選ぶと$\lambda T_i$円の罰金がかかるが、物$\alpha_i$を選ばなければ罰金なしである。

また、項$S_j x(A_{j, 1})x(A_{j,2})... x(A_{j,k_j})$は次のように解釈する:

• 無条件で$S_j$円手に入る。
• 物$\beta_j$を選ばなければ$S_j$円の罰金がかかる。
• 物$\beta_j$を選んだのに品物$\alpha_{A_{j, 1}}$を選ばなかったら$+\infty$円の罰金がかかる。物$\beta_j$を選んだのに物$\alpha_{A_{j, 2}}$を選ばなかったら$+\infty$円の罰金がかかる。……

これらの条件に対応したネットワークを作って最大流を求めると、最小カットの容量$c$も求まる。$\sum S_j - c$が上の不等式の左辺の最小値である。

サンプル1を例にとってグラフを与える:

3 4
4 3 2
4 2 1 10
2 1 2
2 1 3
3 2 3 4

drkenさんのリストにProject Selection Problemの例題として挙がっていたので、そう言われればまあ……という感じだった。

Project Selection Problemについて

• yosupoさんの解説
• 診断人さんの解説