yukicoder No.453 製薬会社:解き方と解答例
現在、yukicoderではAdvent Calendar Contest 2016が開催されています。この記事では、その第4日に出題された、No.453 製薬会社 - yukicoderという問題について、解き方とコードの例を示します。
問題の趣旨
二つの薬品C, Dがあり、これらを組み合わせて二つの製品A, Bを作れる。各製品1 kgを作るのに必要な両薬品の量(kg)は下表の通りである。また、製品A, Bの売価はそれぞれ1000円/kg、2000円/kgである。使用可能な薬品C, Dの量(kg)*1が与えられるので、両製品の売価の合計の最大値を求めよ。
製品A | 製品B | |
薬品C | 3/4 | 2/7 |
薬品D | 1/4 | 5/7 |
解き方
使用する薬品C, Dの量をとすると、最大化すべき売価の合計はと表されます。すると、この問題は次の条件\eqref{1}, \eqref{2}のもとでを最大化するという、一種の線形計画問題になります。
線形計画法、すなわち線形計画問題を解く方法としてはwikipedia:シンプレックス法などがあります。しかしながら、本問の場合には変数がの二つなので、この方法を使う代わりに、座標平面上において条件に対応する領域と直線の位置関係に注意すれば、この問題を解くことができます。具体的には、とある点を共有するように直線を動かしたときの、直線のy切片の最大値に注目すればよいことになります。
二式\eqref{1}、\eqref{2}の等号をとった式が意味する直線をそれぞれとすると、3本の直線の位置関係に着目すれば、次図に示す(i)-(iii)の3つの場合があるとわかります。ここで、紫色の斜線で示したのが領域であり、緑色の点Pはこの中でを最大たらしめるを意味します。
なお、私はGeoGebraで作成したインタラクティブな図(yukicoder No.453の図解 - GeoGebra)で、やを動かしてこの場合分けを考えました。
結局、求める最大値をとすると、これは以下のように具体的に書き表されます。あとはこれをコードにすればよいだけです。
- (i) のとき
- (ii) のとき
- (iii) のとき
コードの例
Haskellによるコードは、たとえば次のようになります。
import Control.Applicative ((<$>)) import Text.Printf (printf) computeMax :: RealFloat a => a -> a -> a computeMax c d | 3.5 * c <= 1.4 * d = v 0 $ 3.5 * c | 1 / 3 * c <= d && 1.4 * d < 3.5 * c = v xp yp | otherwise = v (4 * d) 0 where v x y = 1000 * x + 2000 * y xp = 20 / 13 * c - 8 / 13 * d yp = -7 / 13 * c + 21 / 13 * d main :: IO () main = do [c, d] <- fmap read . words <$> getLine :: IO [Double] printf "%.12f\n" (computeMax c d)
補足:SciPyを使ったコード
yukicoderでは現在利用できませんが、SciPyのscipy.optimize.linprog
を使い、シンプレックス法でこの問題を解くコードは次のようになります。なお、scipy.optimize.linprog
では対象となる関数を「最小化」するので、ここではの最大化をの最小化と読み替えています。
#!/usr/bin/env python3 import scipy.optimize c = [-1000, -2000] A = [[3 / 4, 2 / 7], [1 / 4, 5 / 7]] xb = (0, None) yb = (0, None) def main(): b = [int(x) for x in input().split()] res = scipy.optimize.linprog(c, A_ub=A, b_ub=b, bounds=(xb, yb)) print("{:.12f}".format(-res.fun)) if __name__ == '__main__': main()
感想
レベル★★★ということで少し身構えましたが、落ち着いてよく見ると、以前おそらく数学の問題として解いたことがあるような問題であるとわかり、安心しました。なんだか懐かしい気持ちになりました。シンプレックス法を自分で実装できるようにしたほうがよいのだろうかと、考えています。また、GeoGebraの便利さを再確認しました。
*1:問題文中ではとなっていますが、この記事ではとします。