Marathon Match 32

TopCoder

http://www.topcoder.com/longcontest/?module=ViewStandings&rd=12198
これに参加してました。
暫定で 3 位だったのが System test で一人抜いて 2 位。1 位の人にはあと一歩で追いつけませんでした。

問題は工場の経営者になって、5000日の期間内にどれだけ利益を上げられるかというもの。

最初に

  • 1日あたりの最大生産量（何個の製品を作れるか）
  • 倉庫の大きさ（材料/製品を最大いくつまで持っておけるか）
  • 製品のリスト（どの部品から作られるか。他の製品が部品になることもある）

が与えられます。で、日々「製品aをX個、bをY個をn日以内に」というような契約がいくつか提示されるので受けるか拒否するか選んで、受けた仕事をこなしていきます。

細かいルールがいろいろあって取っつきにくそうな印象でしたが、offline test のツールを落としてきてしばらくいじくり回してると、有効な戦略がなんとなく分かってきました。

  • とにかく生産ラインを使い切る
  • 何を作るかはあまり凝る必要はなくて、納期が近い順に必要なだけ作っていけばOK
  • ただし、倉庫が小さいときは気をつけてやらないと作りかけの製品で詰まる
  • 材料の仕入れ値は日々変わるが、相場で儲けようとは考えない方がいい

あとは受ける契約の選び方が重要です。契約にスコアをつけて、現在持っている仕事の量との兼ね合いで受けるか蹴るか決めるんですが、スコアの計算を

(価格 - 原価 - 予想ペナルティ) / 生産ライン使用量

みたいにしてました。

で終わった後に気づいたんですが、倉庫が小さいときは生産ラインを最大まで使い切れないことが多い（材料を置ききれない）から、単にラインの使用量で割るんじゃなくてその辺を考慮しないといけなかったのでした。
実際 System test の結果を見ると倉庫が小さめのときに負けてるのが多い感じでした。うーん悔しい。