AtCoder Beginner Contest 054 D - Mixing Experiment

お題箱より。

半分全列挙解法を…とのリクエストだったので、そちらを書きます。

解法

$N$ 個の薬品をグループ0・グループ1に分け、それぞれについて薬品の選び方を決めたとします。これらを混ぜてちょうど混合比 $M_{a}:M_{b}$ になっているかどうかを判定する式を立てましょう。

グループ $g$ で選んだ薬品に含まれるタイプAの薬品量を $A_{g}$ 、タイプBの薬品量を $B_{g}$ と表記することにします（ $g$ は $0$ または $1$ ）。両グループの薬品を混ぜて混合比が $M_{a}:M_{b}$ となる条件は

$\displaystyle\frac{A_{0}+A_{1}}{B_{0}+B_{1}} = \frac{M_{a}}{M_{b}}$

という数式で表現できます。これを通分すると

$M_{b}A_{0} + M_{b}A_{1} = M_{a} B_{0} + M_{a}B_{1}$

となりますが、さらにこれを移項して並び替えると

$(M_{b}A_{0} - M_{a}B_{0}) + (M_{b}A_{1} - M_{a}B_{1}) = 0$

となります。このように変形した目的は、グループ0に関する値とグループ1に関する値に分離するためです。

つまり両グループで選んだ薬品を混ぜて欲しい混合比になる条件は、グループ $g$ に対して $S_{g} = M_{b}A_{g} - M_{a}B_{g}$ と定義すると、 $S_{0} + S_{1} = 0$ という数式で表現できます。これはつまり、それぞれのグループで薬品の選び方を決めた時の具体的な薬品量は忘れてしまって良くて、 $S_{g}$ の値さえ覚えておけば判定ができるということです。

求めたいのは欲しい混合比になるための最小価格でした。なのでそれぞれのグループごとに選び方を全列挙して、以下の値を求めます。

$C\lbrack g \rbrack\lbrack s \rbrack =$ グループ $g$ の薬品を1つ以上選んで、その薬品量 $A_{g}, B_{g}$ について $M_{b}A_{g} - M_{a}B_{g}$ の値が $s$ となるときの、最小の合計価格。ただしそのような選び方が存在しない場合はINFとする。

1つ以上という点に注意しないといけない理由は、この条件を考慮しないと両グループともに薬品を1つも選ばないケースが含まれてしまうからです。薬品を1つも選ばないと $S_{0} + S_{1} = 0$ は必ず満たされてしまうので、合計価格0が必ず答えに出てきてしまいます。

欲しい混合比を作れる最小の価格は、以下の3パターンのうちの最も小さいものになります。ただし全ての結果がINF以上になってしまった場合は、ほしい混合比を作れる薬品の選び方は存在しません。

グループ0に属する薬品だけで作る場合。その価格は $C\lbrack 0 \rbrack\lbrack 0 \rbrack$ である。
グループ1に属する薬品だけで作る場合。その価格は $C\lbrack 1 \rbrack\lbrack 0 \rbrack$ である。
両グループの薬品をともに1つ以上選ぶ場合。その価格は取りうる全ての $s$ に対する $C\lbrack 0 \rbrack\lbrack s \rbrack + C\lbrack 1 \rbrack\lbrack -s \rbrack$ の最小値である。

これで解くことができました。ポイントは判定式を立てた後に項をグループごとに分離する、以下の形への式変形ですね。

$(M_{b}A_{0} - M_{a}B_{0}) + (M_{b}A_{1} - M_{a}B_{1}) = 0$

ACコード

$C\lbrack g \rbrack\lbrack s \rbrack$ において $s$ が負になるため、実装上は負のインデックスを回避しないといけません。最小値が0以上になるように固定値を足して管理する（オフセット）か、mapを使うかのどちらかが良いと思います。mapを使うと計算量に $\log$ が追加で乗る点には注意しましょう。