飲料工場が舞台、最適化の手順競う～プログラミングコンテスト

2024.10.21X5:プログラミングコンテスト

第11回プログラミングコンテスト

　アスプローバ社主催の第11回プログラミングコンテストが、2024年9月に行われました。今回の問題は、炭酸飲料の工場が舞台です。甘さと炭酸の強さが異なった飲み物を、効率よく作る手順を見つけることです。４時間の制限時間の中で得点を競いました。9月27日、東京・五反田のアスプローバ本社で、表彰式と懇親会が開かれ、賞金が贈呈されました。席上、上位入賞者が解法を説明し、盛んな質疑応答がありました。

　田中智宏社長は開会のあいさつで、「私たちの会社は、ウインドウズ95の時代から工場の生産スケジューラを作っており、国内だけでなく、海外でも1500本を売り上げました。メイド・イン・ジャパンのソフトウェアは珍しい存在です。今、次世代のスケジューラを開発しており、それはヒューリスティック（人間の思考過程に近い発見的手法）を中軸にしていて、海外でも注目されています。興味があったら仲間に加わってください」と話しました。

貪欲法でやってみると…

　さて今回の問題では、ある飲料工場で、シロップと炭酸水を混ぜ合わせることで炭酸飲料を作ります。それぞれの炭酸飲料は、甘さと炭酸の強さで表現されます。初めは甘さも炭酸も「0」の炭酸飲料だけを持っていますが、操作を行うことで他の炭酸飲料を作成することができます。

　指定された「甘さ」と「炭酸の強さ」を持つ炭酸飲料を作るには、すでに作った飲料にシロップや炭酸水を追加します。加えた分の甘さや炭酸の強さによってコストがかかります。たとえば、甘さ2、炭酸5の飲料を作るには、甘さ0、炭酸0の炭酸飲料に甘さを2足して、炭酸を5加えます。コストは「足した分の甘さ＋炭酸の量」。この場合は「2＋5＝7」です。 N種類の炭酸飲料を作るために、5N回以内の操作を行うことができます。指定された炭酸飲料を作るための操作列の中で、コストの総和が最も小さいものを見つけることが目標です。

　問題の狙いを一言で示すと、「まとめてできる処理をまとめてやる」ということになります。工場の生産計画ではよくみられる方法です。参加者は「組み合わせ最適化」のさまざまな手法を駆使して、問題に挑みました。多くの参加者が採用したのは「貪欲法」（どんよくほう）でした。後先のことを考えず、その場その場での最善の選択を繰り返していく手法です。

　４位に入賞したspawn(スポーン)さんは、こう説明しています。「貪欲オンリーです。クエリ逆順でマージする方針です。x+y（甘味＋炭酸）の大きい方からマンハッタン距離（この場合はコスト）で一番近いものとマージするのを繰り返して解を構成します。これだけだと自明なロスがあったので、今度は順向きに見ていって他の辺の利用を探索します」「クエリ逆順マージの方針に気づいたのと、スコア計算から、できるだけ近い2点をマージするとお得と気づいたのがよかったですね」。 spawnさんはITスタートアップのデータサイエンティストで、プログラミングコンテストでの賞金獲得は初めてだそうです。

　7位に入賞したuwi（うい）さんは「 スコアの95%は貪欲法で達成し、残りの5%は山登り法でコスト削減を試みました。最初に良い方針が出たので、それを軸に最後まで進めました。運が良かったと思います」とコメントしました。uwiさんは7歳からプログラミングを始めた実力者で、これまでに多くのプログラミングコンテストに参加してきましたが、現在は子育て中のため「夜のプロコンは厳しい」と語っていました。

おすすめは焼きなまし法

　出題者であるアスプローバのエンジニア、小島健介さんは「今回の問題はシンプルですが、意外に難しいものです。４時間という制限時間もあるので、貪欲法で着手したくなります。でも実は、焼きなまし法を採用するとうまく行きます」と述べました。焼きなまし法とは、解を繰り返し求め直して、よりよいものを見つけていく方法で、ヒューリスティックと共通した考え方です。

　アスプローバ社では、今後もプログラミングコンテストを通じて、優れたプログラミング技能者を発掘、顕彰し、プログラミング技法の進歩に貢献したいと考えています。

（了）