yukicoder No.453 製薬会社：解き方と解答例 - はむ吉（のんびり）の練習ノート

現在、yukicoderではAdvent Calendar Contest 2016が開催されています。この記事では、その第4日に出題された、No.453 製薬会社 - yukicoderという問題について、解き方とコードの例を示します。

問題の趣旨
解き方
コードの例
補足：SciPyを使ったコード
感想

問題の趣旨

二つの薬品C, Dがあり、これらを組み合わせて二つの製品A, Bを作れる。各製品1 kgを作るのに必要な両薬品の量(kg)は下表の通りである。また、製品A, Bの売価はそれぞれ1000円/kg、2000円/kgである。使用可能な薬品C, Dの量(kg) $c, d$ *1が与えられるので、両製品の売価の合計の最大値を求めよ。

	製品A	製品B
薬品C	3/4	2/7
薬品D	1/4	5/7

解き方

使用する薬品C, Dの量を $x(\ge 0), y(\ge 0)$ とすると、最大化すべき売価の合計は $v(x, y)=1000x + 2000y$ と表されます。すると、この問題は次の条件\eqref{1}, \eqref{2}のもとで $v(x,y)$ を最大化するという、一種の線形計画問題になります。
$\begin{eqnarray}\frac{3}{4}x + \frac{2}{7}y &\le& c\tag{1}\label{1}\\ \frac{1}{4}x + \frac{5}{7}y &\le& d\tag{2}\label{2}\end{eqnarray}$

線形計画法、すなわち線形計画問題を解く方法としてはwikipedia:シンプレックス法などがあります。しかしながら、本問の場合には変数が $x,y$ の二つなので、この方法を使う代わりに、座標平面上において条件に対応する領域 $E$ と直線 $l:1000x + 2000y = v$ の位置関係に注意すれば、この問題を解くことができます。具体的には、 $E$ とある点 $(x_0, y_0)$ を共有するように直線 $l$ を動かしたときの、直線 $l$ のy切片 $v/2000$ の最大値に注目すればよいことになります。

二式\eqref{1}、\eqref{2}の等号をとった式が意味する直線をそれぞれ $l_1, l_2$ とすると、3本の直線の位置関係に着目すれば、次図に示す(i)-(iii)の3つの場合があるとわかります。ここで、紫色の斜線で示したのが領域 $E$ であり、緑色の点Pはこの中で $v(x,y)$ を最大たらしめる $(x, y)$ を意味します。

f:id:hamukichi_nbr:20161210145851p:plain

なお、私はGeoGebraで作成したインタラクティブな図（yukicoder No.453の図解 - GeoGebra）で、 $c, d$ や $(x, y)$ を動かしてこの場合分けを考えました。

結局、求める最大値を $V$ とすると、これは以下のように具体的に書き表されます。あとはこれをコードにすればよいだけです。

(i) $5c/2 \le d$ のとき $V=v(0, 7c/2)$
(ii) $c/3 \le d \le 5c/2$ のとき $V=v(20c/13 - 8d/13, -7c/13 + 21d/13)$
(iii) $(0\le) d\le c/3$ のとき $V=v(4d, 0)$

コードの例

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では対象となる関数を「最小化」するので、ここでは $v(x,y)$ の最大化を $-v(x,y)$ の最小化と読み替えています。

#!/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:問題文中では $C, D$ となっていますが、この記事では $c, d$ とします。