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

https://atcoder.jp/contests/asprocon4 に参加しました。

今回の問題設定で最初に思いつく方針は第3回同様焼き鈍しなんですが、最近焼き鈍し以外の方法を試したい気持ちがあったので別の方針を考えていたらうまくいきませんでした。それで結局残り時間が少なくなってから焼き鈍しに切り替えましたが、いろいろ分析する時間がないと厳しいですね。そもそもいい貪欲法を思いつくまでの時間が長すぎというのもありましたが。

最初にやろうとしたこととか

問題文を読んでみたら、いくつかわからないところがあるので generator のソースを読んでみる。

  • 同じ品目を複数の設備で作れる場合がある。それどころか、1/2ぐらいの設備で作れる
  • 粗利は注文ごとに入力されるが、実は品目ごとの粗利が決まっていて、それとオーダ数との積で算出されている
  • 最早開始時刻から納期までの時間は、各設備での製造時間の平均の2倍と Dmax の min 以上
    • ということは、速い設備が都合よく使えれば間に合う
  • それ以外のパラメータはだいたい一様ランダムと思ってよさそう
    • 製造速度もランダムで 1-200 とかなので特定の品目に関して使える設備は事実上一部に限られそう

焼き鈍しではない方針として最初に考えたもの。

  1. とりあえず貪欲を書く
  2. 貪欲法にランダム要素を入れてみる
  3. ランダム入り貪欲法を使って playout をするモンテカルロをする

最初に、納期でソートしてその順に割り付け先の設備を決める貪欲を書いてみた。これでだいたい2900億ぐらい。このときは単純に粗利からペナルティを引いたもので評価したけど、後で考えてみるとこの評価のしかたは今見ている工程が後ろに続く工程にどういう影響を及ぼしそうかが考慮されてなくて、それほどうまくいきそうにない（例えば割り付ける工程の品目を下手に選ぶと次にすごく長い段取り時間がかかるかもしれない）。

当初の予定では、途中まで割り付けを定めた計画の評価値として、残りを上記の方法で貪欲に割り付けたときのスコアを使うつもりだったのだが、それだと遅すぎるしスコアもそんなによくはない印象。

ビジュアライザで見てみると、無駄な空白時間がたくさんできているようだ。どうも割り付けの順番を固定して後ろへ割り付けていくという戦略はあまりよくなくて、途中の隙間にも入れるとかしないといけないらしい。

焼き鈍してみた

どうもいい方針が浮かばないので、今あるコードに焼き鈍しを入れる最短の手順として、割り付けを決める順番を焼き鈍すということを試してみた。このあたりでとりあえず提出してみたら 2976 ぐらい。たぶん近傍がよくないのと、貪欲法があまりうまくないのだと思ったが、どうにも解決策が浮かばず。

とりあえず同じ品目がもっと並んでいてほしい気がしたので、ランダムに区間を選んで品目番号でソートするとかいう強引なことをしてみたら、スコアは上がったが 2993 ぐらいで 3000 までまだだいぶ距離がある。

貪欲法を改善してみるなど

やっぱり初期解が悪すぎるのではという気がして、別の貪欲法を考えた。注文と設備の組を全通り試して、割り付けたときにその前にできる隙間時間と段取り時間と終了時刻の和が最小になる組を次に割り付ける、という貪欲をやったらそれだけで 2990 ぐらいになった。前の初期解が 2900 ぐらいだったのでだいぶよくなった。

あとは結局焼き鈍し。各設備についてどの注文をどの順番で処理するかを決めると最適な割り付けは自明に定まるので（asprocon3 と同じで、できるだけ早い時間に割り付けていけばよい）、それを焼き鈍した。近傍は単純で、同じ設備の二つの工程のランダム swap と、ランダムに選んだ工程をランダムに選んだ別の場所へ移動するのを試した。

これだけだとあまりにも単純なので、いろいろ近傍を工夫しようとしたけど何をしてもよくならなかった。以下考えたこと（なんか全部スコアが下がった）。

  • 同じ品目どうしの swap でないとほとんどよくならないので同じ品目の組が高確率で選ばれるようにする
  • あまり時間的に離れた組の swap や離れたところへの移動をしても改善しそうにないので、ある程度移動範囲を絞る
  • ある工程を別の設備に移動する場合、前後どちらかに同じ品目があるところへ移動する確率を高くする
  • swap や移動の距離の上限を、時間経過とともに小さくする（焼き鈍しの温度を下げるのと同じ要領）
  • 納期遅れの発生している注文を高確率で選ぶようにする

あと細かい高速化。

  • 遅延がないときに penalty の計算をしない（浮動小数点数の演算があるのでけっこう違いが出る）
  • スコア計算式の粗利のところは全注文の pr の総和が足されるだけなので、入力を読んだときに総和を覚えておいて、あとで足せばよい
  • a はペナルティ計算のときしか使わなくて必ず pr/a の形で出てくるので、はじめから pr/a だけ覚えておけばよい