No.054 D

半分全列挙を使う.

$N$ 種類の薬品を前半と後半に分け, 後半を先に全探索しておき, 前半の組み合わせごとに後半の全探索の結果の中から最適なものを選ぶ.

残りは後半の全探索の結果の中から最適なものを選ぶにはどうすればいいかという問題である.

まず, 混合比が $M_a : M_b$ にならなければいけないので, タイプA, Bの物質の量はそれぞれ $(kM_a, kM_b)$ とならなければいけない. ($M_a, M_b$ は互いに素である)

前半の組み合わせにおけるタイプA, Bの物質の量を $(A_1, B_1)$ として後半の組み合わせにおけるタイプA, Bの物質の量を $(A_2, B_2)$ とすると, $A_1 + A_2$ は $M_a$ で割り切れなければいけないので, $A_2$ は $M_a$ で割った余りで分類しておく. 同様に $B_2$ も $M_b$ で割った余りで分類しておく.

さらに

$$\lfloor A_1/M_a \rfloor + \lceil A_2/M_a \rceil = \lfloor B_1/M_b \rfloor + \lceil B_2/M_b \rceil$$

となるので,

$$\lfloor A_1/M_a \rfloor - \lfloor B_1/M_b \rfloor = \lceil B_2/M_b \rceil - \lceil A_2/M_a \rceil$$

となり, $\lceil B_2/M_b \rceil - \lceil A_2/M_a \rceil$ で分類する.

$A_2$ を $M_a$ で割った余り, $B_2$ を $M_b$ で割った余り, $\lceil B_2/M_b \rceil - \lceil A_2/M_a \rceil$ で分類すればこの分類の中での最安値を使うのが最適なので, それより高い組み合わせは保存しておく必要がなく, 後半の全探索の結果の中から最適なものを選ぶ計算量は $O(1)$ となる.