2nd Asprova Programming Contest 参加記
AtCoder上で行われた2nd Asprova Programming Contestに参加して、最終結果84人中10位でした。マラソン系のコンテストは初挑戦でした。記念に振り返りを書き残しておきます。なお、このコンテスト終了直後にTopCoderのMM106にシフトした結果1週間以上経ってしまっているのでかなり記憶があやふやです。
参加(12/28)
ratedのコンテストあるかな～と「予定されたコンテスト」欄を眺めるたびに目に入っていた謎のコンテスト。ページを覗いてみると期間が数週間あって、出来るだけ得点を最大化するいわゆるマラソン系のコンテストらしい。そして問題がめちゃくちゃ面倒そう。しばらくは全く参加する気がありませんでした。
しかしICFPCやマラソンマッチの紹介記事などを見て前からマラソン自体には興味があったので、冬休みでそこまでやることもないしということで意を決して飛び込むことに。
問題を把握(12/30)
問題はこちら。
https://atcoder.jp/contests/asprocon2/tasks/asprova2018_a
問題文は本当に長くて制約も面倒なのですが、辛うじて一文でまとめるなら「複数の工程から製造される製品とそのそれぞれの工程を担当できる機械などの情報が与えられるので、納期や数量、着手可能時刻が指定された大量のオーダーを効率良く捌くプログラムを作れ」というもの。
実際にはさらに様々なパラメータがあって、スコアの計算式（重視される要素）もテストケース毎に指定されます。
いきなりコードを書ける状態ではなかったので、2日間はどのようなアルゴリズムが使えそうかひたすら考えていました。
初提出(12/30)
まず考えられた解法は、時刻T=0からタイムステップを進めて行って、着手可能な状態のオーダーについて納期などの優先度で待ち行列を保持し、それぞれ使う機械を決めて順番に製造ラインに放り込んでいく愚直なシミュレーションです。
親切にも貪欲法によるサンプルプログラムが用意されていたので、これを軽く書き換えて手元でテスト。結構あっさり思い通りに動いてくれたので、提出してみる。4110億点くらいで、サンプルのままの点数（4083億点くらい）より若干高い程度でした。まあこんなもんかなという気持ち。
推敲
シミュレーションは当然現実に近づけた方が正確だからタイムステップは1（単位時間）にするべきだろうと思っていたのですが、TLEするので仕方なく適当に大きく取ってみたらかなり伸びました。4460億点に到達。
また、この問題では「段取り時間」がなかなか重要で、各機械ごとに直前に製造していた品目との相性によって段取り時間（無駄な余白）が大きく変わります。つまり、処理するオーダーの順番以外に、「どの機械に担当させるか」を吟味しなければなりません。
サンプルを流用したままだとこれが何も考えられていない（その工程を担当できる機械ならなんでもOK状態）なので、最も相性が良い機械を選ばせるようにしました。
4466億点まで上昇。(12/30)
あと、Pythonでビジュアライザらしきものを作ってみました。スケジュールからこんな感じの画像を生成します。
使い勝手は良いと言えるものではありませんでしたが、どんなところが無駄になっているか、などを把握するのは事足りていたので結局最後までこのまま使い続けました。
さらに、着手可能になったオーダーを並ばせる順序は単に納期だけを基準にすると雑すぎるので、残りの工程数など要素を複雑に足して、それぞれに定数のパラメータを設定しました。
このパラメータは問題設定によってどれが最適かはかなり変わってくるので、それぞれいろいろに変えながら数十パターンでシミュレーションを回し、もっともスコアが良かったものを解として採用させることに。（1パターンのシミュレーションは最大数十msで済む）
また、解を作り終えた後、せっかく2000msの時間が与えられているのだからギリギリまで自明な改善点は改善させればいいのでは？と考えました。
マラソン勢からは突っ込まれてしまいそうですが、この時までの私は、マラソンマッチにおいて探索&ループの繰り返しが常套手段であることを知らず、解析的に一発生成して終わりだと思っていました。山登り法や焼きなまし法という概念も知りません。再発明の状態です。
各機械上のスケジュールの適当な隣接部分を入れ替えて時刻を再生成し、スコアを求めて元より良くなっていればそれを採用（いわゆる山登り法）としたところ、4490億点の壁を越えました。(12/31)
あとはこれを、単純なランダム選択以外に改善が見込めそうな箇所を探して操作したり、使う機械を入れ替えたりという操作を適当な配分で織り交ぜながら各箇所の処理をチューニングし、4493億点まで到達。(1/5)
その後伸び悩んでいたのですが、初期スケジュールの生成のたった一箇所の条件式を2文字変えてみたら4497億点に飛躍。(1/6) 数日前なら入賞圏内の得点でした。
