カレーに入れる最適なカレールーの量を二分探索して調べたら地獄だった

1.はじめに

この記事は競プロ Advent Calendar 2021の19日目の記事です。

私は競プロを始めて1年半くらいが経過しました。専門学生時代には毎日問題を解き、社会人になった今でも仕事と回線の問題で毎日ではありませんが、気が向いたときに問題を解いています。

競プロでは様々なアルゴリズムを使いますが、私は思いました。

現実で使わん！！！

少なくとも、私が過ごしている中では Union-Find やダイクストラ等使う必要性が出てこないし、仕事では VBA で if、for、while を使って簡単なマクロを作るレベル。

せっかく覚えたアルゴリズムを使わずに終わるのはもったいないということで、今回は現実でも扱いやすそうな二分探索に焦点を当てていこうと思いました。

2.二分探索のテーマ決め

ところで、私はスパイスハーブ検定を受けるためにスパイスについて勉強してきました。そういえば、カレーはたくさんのスパイスを混ぜ合わせて作られている、それを凝縮したのがカレールーということをふと思い出しました。そんな凝縮されたカレールーなのだから、分量より多く入れた方がおいしさが爆上がりするのでは？、と考えてませんが、誰かにそそのかされたのでやることにしました。

結果的に、この誰かを恨むことになるとは、この時はまだ思っていませんでした。

3-1.カレーの作り方

では早速カレーを作ろう！と思いましたが、カレールー以外の条件は固定しないと、味に変化があり、正確な結果にならないと考えました。そこで、以下のルールを決めました。

• カレールーはスパイス&ハーブ検定に協力している S&B(エスビー食品株式会社)のものを採用
• カレールーは 1 箱に 2 パック入っている。1 パックの 1/4 を 1 個、1 パックを 4 個、1 箱を 8 個とする
• 野菜を毎回切っていては大きさや品質にばらつきが出ると思い、冷凍されているカット野菜を採用
• カレーに使う材料はカット野菜(100g)、水(400ml)と、二分探索でばらつきが出るカレールー、少量のサラダ油のみトッピングや具を足すことは絶対にしない
• 別途ご飯(１合)を炊く

また、作り方も灰汁取りなどの工程は省き、シンプルにしました。

• サラダ油でカット野菜を炒める
• 水を入れて沸騰するまで待つ
• カレールーを入れてふたをする(時々かき混ぜる)
• 完全にカレールーが溶けたら皿にご飯と一緒に盛って完成

今回はこのルールで作っていきます。

ちなみに、このルールで作ると 2 人前になると思います。

3-2.二分探索の疑似コード作成

ルールが決まったところで、今回の二分探索の疑似コードを書こうと思います。

ok = 0
ng = 32

while ng - ok > 1
    x = floor((ok + ng) / 2)
    Curry = x 個のカレールーで作ったカレー
    if Curry は美味しい
        ok = x
    else
        ng = x

とりあえず(予算の都合で)カレールー 2 箱分から始まるように値を調整しました。頑張ってカレーを作りたいと思います。

3-3.二分探索開始

探索の状況は分かりやすく図にしておきます。

では、最初のカレーはルー 2 箱分のカレーです。早速作っていきましょう。

野菜を炒めて、

水を入れて、沸騰した水にカレールーを入れ...

2 箱分のカレールーを入れたカレー、思った以上にひどかった。

そのまま煮込むと...

なんか泥ができた、これは泥でしかない。

皿に盛ってみたが、カレーにスプーンがささって立った。 絶対に美味しくないと思うが、一応食べた。

ﾊﾟｸｯ

まず口の中に広がったのは食塩の風味、そして食塩の味が口いっぱいに広がり続けました。さらに食塩の後味が口の中に残り続けた。近くにあったアクエリアスを飲み干してもなお、残り続ける食塩感に嫌気がさした。カレールーには結構食塩が使われているみたいです。

このカレーは致死量のカレーと呼ぶことにしました。もちろんおいしくなかったので ng = x です。

ここで重大なミスをしました。8 個と 4 個の写真を撮り忘れてしまいました。 どうしようかと悩みましたが、泥と少しマシな泥をもう一度作りたくなかったので妥協することにしました、時間もなかったし。

ここまで、4 個以上カレールーを入れるとまずいことが分かりました。スパイスを入れすぎるということをオーバースパイスといい、今回はオーバースパイスで濃いカレーができてまずいかな、と考えていましたが、普通に食塩で死ぬと思いませんでした。

次はカレールー 2 個のカレーです。

普通のカレーができました。3 日間泥を見続けたからか、普通のカレーができただけでかなり嬉しかったです。

一口食べて、あまりのおいしさにスプーンが止まらず、勢いで完食してしまいました。この企画初めてのおいしいカレーに涙が止まりませんでした。もちろん ok = x です。

そして、今回最後となるカレールー 3 個のカレーです。

今までの泥と比べたら食べれないことはないものの、塩気が強く少し美味しくないと思いました。ng = x とします。

3-4.二分探索結果

二分探索の結果、カレールー 2 個のカレーが一番おいしいとわかりました。というより、分量をキチンと守って料理作れカスって話でした。

もう少しカレールーを使うと思って買いだめをしたんですが、だいぶカレールーが余ってしまいました。

「もうカレーはこりごりだよ～！」

完

4.あとがき

今回は二分探索を取り上げました。毎回半分の要素が探索済みになるため、10の18乗の要素数でも約60回くらいの探索で答えを求めることができます。

「伝家の宝刀二分探索」とも言われ、応用がしやすいので絶対に使えるようになりたいアルゴリズムです。

リストが昇順か降順、または答えが線型でないと使えない点に気を付けましょう。

スパイス&ハーブ検定、受かってるといいな。