未確定の注文に応じる最適の生産量～プログラミングコンテスト

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

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

アスプローバ社主催の第12回プログラミングコンテストが、2025年9月に行われました。今回の問題は、需要の動向に応じて、無駄のない生産量を探し出すという狙いで作られました。9月26日、東京・西五反田で、表彰式と懇親会が開かれ、賞金が贈呈されました。席上、上位入賞者が解法を説明し、盛んな質疑応答がありました。

複雑な現実もプロコンから

田中智宏社長は開会のあいさつで、「日本には300人以上の大工場が1万もあり、日々生産計画という難問を解いています。私たちの会社は、次世代のスケジューラSolverを開発しており、すでに数十本が生産現場に投入されて、お客さまに喜んでもらっています。今年は海外でも使われ始めました。現実の問題は複雑ですが、コンテストの延長線上にあります。興味があったら仲間に加わってください」と話しました。

【問題】需要の動向に応じて、無駄のない生産量を探し出す

さて今回の問題は次のようなもので、計算の実行時間は２秒に制限されています。

N 枚の何も書かれていないカードと、L 以上 U 以下の整数値を一様ランダムかつ独立に M 個生成する乱数生成器がある。これらを使って以下のゲームを行う。

1. 最初に 1 以上 U 以下の整数 A₁,…,A_N を自由に選び、i 番目のカードには A_i を書き込む
2. 次に乱数生成器により M 個の整数 B₁,…,B_M が生成される
3. 0 枚以上の好きな枚数のカードを捨て、捨てなかったカードを M 個の山に分ける（空の山があってもよい）

ゲームの目標は、j 番目の山のカードに書かれた数の合計を B_j に近くすることである。

問題を作成したアスプローバ社のエンジニア・小島健介さんは「Ａは在庫、Ｂは注文に相当します。普通の問題ならば、ＡとＢの値は両方とも与えられるのですが、それでは目新しさに欠けるので、Ａも出力するようにしました」と言います。つまり、注文は未確定ですが分布は分かっているという状態で、どのように生産し在庫を持てば無駄が最小となるかを求めるのです。

上位の方による解法の解説

解に至る方法は多様でした。席上、上位入賞者の伊森友樹さん（ニックネーム:olphe）、tomerunさん、佐藤遼太郎さん（ニックネーム:hitonanode）の3人から発表があり、いずれも貪欲法、焼きなまし法などを組み合わせており、アプローチが異なっていました。大きな失敗を防ぎながら、細かい調整を行って改善していくという方法は、おおむね共通していたようです。全体で２位となった伊森さんは「ヒューリスティック（正解に近い解を素早く求める）のコンテストでは一番いい順位でした。得意な問題を出してもらって感謝しています」と話しました。優勝者はyosupoさんでした。上位入賞者には、順位に応じて8万円から1万円の賞金が贈られました。

小島さんによると、生成ＡＩを用いてこの問題を解くと、ある程度のレベルの答えは出てくるのですが、上位入賞者の水準には及ばないそうです。

中学生の入賞者も

今回は「学生賞」が新たに設けられ、上位入賞者に5000円が贈られました。香川県の中学3年生tyokousagi（ちょこうさぎ）さんが大学生らに交じって5位に入りました。ご家族と一緒に表彰式に参加し「プログラミングはまだ1年ほどの経験しかないのですが、進学後もこの分野をやっていきたい」と意欲を見せていました。

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