はじめに

京都大学の生協食堂には「ミール」というシステムがあります。

このシステムは、簡単に言うと学食版の定期のようなものです。
年度初めに1年間の食堂代としてお金を払っておくことで、1食550円分はお金を払わずに利用できるシステムです。4月から一人暮らしをする大学生を持つ親からすれば、万が一お金がなくても食堂にいけば、栄養のある料理を食べることができるので、親にお金を払ってもらって利用している人も多いです。

しかし、授業がない平日や土曜日、夏休みなどの大学に来る必要がない日でも食堂を利用し続けないと、ほぼ元が取れないという落とし穴もあります。(余った分は年度末に繰り越ししたり手数料数百円を差し引いて返金してもらうこともできます。)
反対に、毎日食堂を利用し続けると、最初に払った分より多くの利用することができるので、ミールで得をするために休みの日も食堂を利用する人のことを京大では「ミール奴隷」と呼んだりします。

このミールは1食550円が限度になっているのですが、このことから、「食堂では550円で栄養的に満足な食事が取れるようになっています」ということをミールを提供する生協はいっているわけです。京大の食堂は、カフェテリア形式なので、いろいろな料理の組み合わせが考えられますが、適切に組み合わせることで550円以内でバランスの良い食事にすることができると捉えることができます。

ここで、「本当に550円で栄養的に満足な食事をつくることができるのか」という疑問が生じます。この疑問は結構難しい問題で、京大生が1回生から抱く疑問でありながら、毎日食堂を利用する京大生であっても4年間この疑問が解決しないまま卒業する人がほとんどでしょう。

そこで、今回はミーラー、特にミール奴隷の方のために、栄養的に満足な組み合わせは550円以内で作ることができるのかを検証しようと思います。

評価基準

「栄養的に満足な」献立の基準、つまり最適解の基準について決めておきます。

食堂では、それぞれの料理に含まれる食材や栄養に応じて、赤･緑･黄の点数がついています。レシートを確認すると、自分の組み合わせについて合計で何点あるか知ることができます。またレシートの下の方に、「1食の目安」として、各色について何点必要かが書いてあります。

そこで、食堂が示している3色の点数を基準とすることにしましょう。

今回の最適解は、「それぞれの色について、1色の目安を満たす組み合わせのうちで、最も合計金額が安いもの」とします。

データ

食堂のメニューはおおよそ週替わりなので、その日の食堂のメニューの価格と点数のデータを得る必要があります。

今回は、食堂のメニューがこのサイトで見ることができるので、ここからスクレイピングすることにします。また、今回は京大の食堂のなかの、北部食堂の最適解をします。

北部食堂のメニューの一覧は以下のページで見ることができます。

https://west2-univ.jp/sp/menu.php?t=650113

メニューついてのページも見てみましょう。例えば、塩だれカツ丼は

https://west2-univ.jp/sp/detail.php?t=650113&c=819043

メニューのURLには、"t=XXXXXX"は食堂を表すパラメーター(北部食堂とか中央食堂とか)と、"c=XXXXXX"にはメニューを表すパラメーターがついています。

そこで、一覧のページからメニューのIDを取得して、各メニューのページから価格と点数を取得することにしましょう。

今日のメニューの一覧を取得する

まず、一覧のサイトからメニューのIDを取得します。一覧のページには、必ずメニューページへのリンクが入っているはずなので、それをスクレイピングします。

しかし、このサイトにはトラップがあって、そのままHTMLを取得すると、主菜のリンクしか取得することができません。実は、副菜やどんぶりなどは、一度折りたたみを解除しないとリンクが現れないのです。

そのため、IDを取得する前に、このボタンをクリックする必要があります。ページのソースを見ると、ジャンル毎に"id=on_a"や"id=on_c"と入っているので、これについているボタンを押してからHTMLを取得します。

後のために、丼やご飯のメニューは別で取得しておきます。(理由は後述)

get_menu.py

import asyncio
from pyppeteer.launcher import launch
from pyppeteer.page import Page, Response
from pyppeteer.browser import Browser
from pyppeteer.element_handle import ElementHandle
import time
import re

#メニューサイトのHTMLを取得する
async def extract_html(push_buttons) -> str:
    # push_buttons:ボタンを押したいジャンルの"on_XX"の「XX」が入っているリスト
    # ブラウザを起動。headless=Falseにすると実際に表示される
    browser: Browser = await launch()

    try:
        page: Page = await browser.newPage()

        # 北部食堂のメニュー一覧のサイトへ移動
        response: Response = await page.goto('https://west2-univ.jp/sp/menu.php?t=650113')
        if response.status != 200:
            raise RuntimeError(f'site is not available. status: {response.status}')

        for x in push_buttons:
            # 押したいボタンを指定してクリック
            buttons: ElementHandle = await page.querySelector('#on_' + x)
            await buttons.click()
            # サイトに負荷を掛けないように時間を空けましょう
            time.sleep(1)

        # ボタンを押した後でHTMLを取得
        html: str = await page.content()

        return html
    finally:
        await browser.close()

#b:副菜、e:デザート、bunrui1:オーダーコーナーのボタン
#主菜は元からボタンが押してある扱いなので、主菜、副菜、デザート、オーダーの情報が入っているHTMLが取得できる。
html: str = asyncio.get_event_loop().run_until_complete(extract_html(["b", "e", "bunrui1"]))

#正規表現を用いて、メニューのIDを取得する
menu = re.findall(r';c=.*">', html)
#menuには';c=XXXXXX">'を満たす文字列が入っています。


#同じようにして丼についてもHTMLを取得する。d:丼のボタン
#こちらは、主菜と丼の情報が入っているHTML
html: str = asyncio.get_event_loop().run_until_complete(extract_html(["d"]))

#正規表現を用いて、メニューのIDを取得する
menu_domburi = re.findall(r';c=.*">', html)

これで、menuの中の"c=XXXXXXX"を取り出すことで、IDを取得できます。

価格と点数を取得する

メニューのIDを一覧を手に入れたので、次はそれぞれのメニューの価格と点数を取得します。

この作業は、取得したIDをからメニューのページに飛んで、そのままHTMLを取得すれば良いですが、2つ注意する点があります。

1つ目は、menuとmenu_domburiには主菜のIDが重複して入っていることです。同じメニューについて何度も価格を調べる必要はないので、IDが重複してないか調べてから価格などを取得しましょう。

2つ目は、ご飯や丼のメニューにはサイズがあることです。塩だれカツ丼やカレーなどの丼メニューはS,M,Lサイズが選ぶことができますが、取得したIDではMサイズの情報しか得られません。

それでは、他のサイズのメニューの情報は得ることができないかというと、そんなことはありません。

なんと、丼のMサイズのIDについて、ID±1のIDを調べるとそのメニューのS,Lサイズのページを開くことができます¹。明日から使えない雑学ですね。ちなみに、白ご飯については、SS、LLサイズもありますが、これはID±2で開くことができます。

以上に気をつけて、メニューのIDのリストを作り、それぞれのメニューについて、HTMLから、名前、価格、点数を取得しましょう。

get_menuinfo.py

menu_id = set()

for s in menu:
    menu_id.add(s[3:-2]) # IDの文字列だけを取り出す

for s in menu_domburi:
    # 丼のメニューだけを追加する
    if s[3:-2] not in menu_id:
        # IDが6桁ではない場合は、Mサイズしかない(多分)
        if len(s) != 11:
            menu_id.add(s[3:-2])
        else:
            # S,Lサイズも追加する
            n = int(s[3:-2])
            # 814702は白ご飯のID
            # 通常の丼はS,M,Lサイズ、白ご飯はSS~LLサイズ
            if n != 814702:
                for i in range(3):
                    menu_id.add(str(n-1+i))
            else:
                for i in range(5):
                    menu_id.add(str(n-2+i))

print(menu_id, len(menu_id))

from urllib import request

def get_info(id):
    # サイトに負荷を掛けないように時間を空けましょう
    time.sleep(1)
    # IDからhtmlを取得
    response = request.urlopen("https://west2-univ.jp/sp/detail.php?t=650113&c=" + id)
    content = response.read()
    response.close()
    html = content.decode()

    # メニュー名を取得
    name = re.search(r"<h1>.*<span>", html)
    name = name.group()[4:-6]

    # 価格
    price = re.search(r"\d+</strong>円", html)
    price = int(price.group()[:-10])

    # 点数
    # 点数は小数点第1位まで示されているので、後の計算のために10倍して整数型で記録しておく
    rgy = re.findall(r".：\d+.\d", html)
    if rgy:
        r = [0] * 3
        for i in range(3):
            if len(rgy[i]) == 5: # 点数が10点未満(X.X点のとき)
                r[i] = int(rgy[i][2] + rgy[i][4])
            else: # 点数が10点以上(XX.X点のとき)
                r[i] = int(rgy[i][2:4] + rgy[i][5])
        return name, [price] + r # 名前,[価格,赤,緑,黄色]をリターンする
    else: #万が一点数を取得できなかった場合
        return

menu_list = dict()

for id in menu_id:
    menu_info = get_info(id)
    if not menu_info:
        name = menu_info[0]
        info = menu_info[1]
        menu_list[name] = info

menu_listを見ると、今日のメニューの名前と、価格、各色の点数の10倍の値を確認することができます。

最適解の計算

価格と点数のデータをそろえることができたので、最適解を計算しようと思います。

最適解を決めるに当たって、今回は同じメニューは1つしか取らないという条件を追加しておきます。食堂には20~30種類くらいのメニューがあるので、ほとんどの人が同じメニューをいくつも頼むと言うことはないと思います。また、同じメニューを何皿も食べるのはバランスのいい食事だとは思えないので、一応問題ない条件だと考えてよいと思います。

ただし、サイズ違いのメニューについて、例えば「塩だれカツ丼M」と「塩だれカツ丼L」は、別々のメニューとして扱い、この２つを同時に頼むのは許容しようと思います。(これが最適解になるならそういうことだと思うことにしましょう。)

さて、具体的な計算方法について考えようと思います。最もシンプルな計算方法として、全ての組み合わせを作って、条件から最適な組み合わせを調べるという方法が思いつきます。

組み合わせの総数は、メニューが$N$品あるとき、すべてのメニューについてそのメニューを取る･取らないの$2$通りあるので、メニューの組み合わせの総数は$2^N$通りある事が分かります。

日によりますが、北部食堂ではサイズの違いをメニューを含めて、だいたい$N=40$品程度あります。よって、コンピューターの力で$2^{40} \approx 10^{12}$通り,、つまりおよそ1兆通り全て計算すれば、最適解を計算できそうです。

しかし、実はコンピューターでも1兆通り全ての計算するには、少し時間がかかってしまいます。競技プログラミングをやっている人ならご存じかと思いますが、コンピューターの計算は$10^9$回がだいたい1秒に相当するので、大雑把に計算すると$10^{12}$回は$1000$秒 $\approx15$分くらいかかる事が分かります。

15分くらいならまだ問題ないかもしれませんが、例えばここから10品増えて$N=50$になると少なく見ても1週間はかかってしまうので、もう少し工夫して速く計算できるようにしたいです。

動的計画法

そこで、最適解を素早く計算できるアルゴリズムとして、動的計画法を使おうと思います。こちらも競技プログラミングではおなじみですが、難しいので説明は他の記事に任せようと思います。

こちらが参考になると思います。
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ナップサック DP 編～

今回は、ナップザック問題を応用したものになります。
先に計算量について確認しておきましょう。品数を$N$、3色の点数の基準の10倍の値をそれぞれ$R,G,Y$とすると、計算量オーダーは$O(NRGY)$になります。$N$については、指数のオーダーから線形のオーダーになったので、品数が増えても計算時間が爆発的に増えると言うことはなくなりました。²
男性の目安を使って計算すると、どんなに大きくに見積もっても$10^8$程度にしかならないので、秒単位で計算できそうです。(Pythonを使っていて、あまりよいプログラムではないので、実際にはもっとかかるかもしれません。また、Pythonにはこれと同じ最適化をしてくれるライブラリがあるので、それを使った方がいいと思います。)

今回の動的計画法では、
$dp[i][r'][g'][y'] = i品目までメニューで、赤:r'点、緑:g'点、黄:y'点を獲得できる最小の費用とその組み合わせ$
を覚えておいて計算します。
$r',g',y'$については、$0.5$点のように小数のまま扱うとたいへんなので、$r = 10r'$として、整数の形で扱えるようにします。このために、あらかじめ点数を10倍した値を記録しておきました。

ただし$dp[i+1]$を計算するためには、$dp[i]$があればよく、$dp[i-1]$は覚えておかなくてもいいので、実際には$dp[i+1][r][g][y]$と$dp[i][r][g][y]$の2つを持っておきながら計算を進めています。

saiteki.py

N = len(menu_list) # 品数
R = 27 # 赤色の点数(×10)
G = 10 # 緑色の点数(×10)
Y = 57 # 黄色の点数(×10)

dp = [[[[10000, set([])] for i in range(Y+1)] for i in range(G+1)] for i in range(R+1)]

dp[0][0][0][0] = 0

# 実際に遷移を計算します
for name, info in menu_list.items():
    # ndp = dp[i+1], dp = dp[i] として計算しています
    ndp = [[[[10000, set([])] for i in range(Y+1)] for i in range(G+1)] for i in range(R+1)]
    price, red, green, yellow = info
    for j in range(R+1):
        nr = min(R, j+red)
        for k in range(G+1):
            ng = min(G, k+green)
            for m in range(Y+1):
                ny = min(Y, m+yellow)
                if ndp[j][k][m][0] > dp[j][k][m][0]:
                    ndp[j][k][m][0] = dp[j][k][m][0]
                    ndp[j][k][m][1] = dp[j][k][m][1]
                if ndp[nr][ng][ny][0] > (price + dp[j][k][m][0]):
                    ndp[nr][ng][ny][0] = price + dp[j][k][m][0]
                    ndp[nr][ng][ny][1] = dp[j][k][m][1] | set([name])
    dp = list(ndp)

def output(t):
    for i in range(0):
        print()
    print("-------------------")
    print("{}円".format(t[0]))
    for x in t[1]:
        p, r, g, y = menu_list[x]
        print("{}  {}円 赤:{}点　緑:{}点　黄:{}点".format(x, p, r/10, g/10, y/10))
    print("--------------------")

#dp[R][G][Y]には最適解の値段と、その組み合わせが入っています。
output(dp[R][G][Y])

結果発表

このプログラムを順につなげると、自動でメニューと価格･点数を取得して、最適解を自動で計算することができます。

実際に計算してみましょう。

結果

-------------------
398円
ほうれん草  66円 赤:0.0点　緑:0.2点　黄:0.0点
大学芋  88円 赤:0.0点　緑:0.8点　黄:1.2点
牛乳  85円 赤:1.7点　緑:0.0点　黄:0.0点
ライス  115円 赤:0.0点　緑:0.0点　黄:5.1点
温泉玉子  44円 赤:1.0点　緑:0.0点　黄:0.0点
--------------------

本日の最適解は398円でした。
実際に食堂でそろえてみるとこんな感じでした。

レシート

考察

少しだけ考察します。
副菜ばかりで、男子大学生が食べるにしては微妙な献立になりました。
これは、栄養的には最適なのでしょうが、食事としてはとても毎日食べられたものではないですね。やっぱり主菜がほしいですね。

メニューの組み合わせを見ると、それぞれの色に特化した副菜を寄せ集めた感じになりました。やっぱり、緑が0.8点ある大学芋はチートということが分かりました。主菜は3色全てに点数がついているのですが、値段に対して点数の効率が良くないという事なのでしょうかね。

結論

ミール(550円)で栄養的に満足な食事を取ることはできます。

まだまだ遊べるプログラムなので、続くと思います。

メニューや日によって、Mサイズしか出していないこともありますが、これは食堂に行かないと確認できないので、今回は他のサイズも注文できるということにして計算します。また、オーダーメニューでも、丼系のメニュー(天津飯とか)の時はS,Lサイズがある場合もありますが、こちらはMサイズしかないとして計算します。 ↩
例えば、最初の方法では2品増えると計算時間が4倍になるのに対して、動的計画法を用いると、品数が2倍になっても計算時間は2倍に収まります。 ↩