はじめに

第6回Asprovaプログラミングコンテストで提出回数部門と得点部門でダブル優勝しました！ 1位を維持するのに必死になっていたため最終的に109回提出しました。

どうだ気持ち悪いレベルの執念深さだろう？ https://t.co/3MJRReB8Pi
— こたまねぎ (@small_onions) 2020年5月6日

解法

高速化のため、下準備として処理の単位として864秒などの3桁秒ごとで動作を決めていく事にする。

基本的には、粗利/(納期遅れ許容時間数量かかる時間) をオーダの評価関数として貪欲に割り当てていく。納期遅れによるペナルティが発生中のオーダーは評価値にさらに4を掛ける。

最初に段取り時間が発生しないオーダーは優先的に割り当てる。次にまだ割り当てがないパン焼き機にオーダーを割り当てていく。最終的にパン焼き機にオーダーがある程度貯まった場合のみ実際に稼働させる。オーダー分割については、できるだけ大きい個数が取れるように適切に分割していく。雑に分割するとオーダー分割の個数の最小要件を満たせずに詰みになるケースが存在するので注意する。

乱数ガチャ要素として、単位秒の設定とパン焼き機を見る順番と採用する評価値の下限の3つを加えた。

工夫

手元で実際に動作させると、特にオーダー数10000のケースでTLEの危険性がかなり高い事がわかる。そこで安全策を取ってオーダー数10000の場合は試行回数は2回に抑えた。

評価関数を調整していると、1000ケースでテストした場合に一部のケースが0点になる事に気づいた。そのようなケースは評価関数を安定寄りに設定すると減るが、逆にプレテストの結果が悪くなってしまった。結局妥協して安定性を取ったせいで朝起きるとプレテスト4位になっていて本当にこれで良かったのかと自問自答していた。システス後の結果を見るとこれで良かったらしい。ビビらせやがって。