第8回Asprovaプログラミングコンテスト参加記
第8回 Asprova プログラミングコンテストの参加記です
1位!って記事を書く予定でしたが、システムテストで2位に落ちてしまいました、残念
問題
問題文は参加者しか見えないように設定されてるので省略します。
雑に言うと、(サイズ、色）のペアで特徴づけられる製品達が与えられるので、それをベルトコンベアに効率よく敷き詰めていく問題です。
ただし、サイズが異なる製品や色が異なる製品を隣同士に配置するには一定の距離を空ける必要があり、また、同時にベルトコンベア上に存在できる同サイズの製品の個数に制約があったりします。
大まかな方針
情報が事前に全部与えられてる系の問題は大抵ビームサーチか焼きなましです。
ビームサーチでいい感じの解法が作れそうなときは最終的にビームサーチのほうが強いのですが、今回の問題設定では状態の管理などが難しそうで諦めました。
焼きなましと言っても個人的には2種類あると思っていて、軽い遷移を多く繰り返す焼きなましと重い貪欲法を繰り返す焼きなましです。
前者は局所性が高いときに強くて後者は局所性が低いときに強い印象を持っています。
今回の問題を見たとき、前半を少しいじると後半が大きく崩れてしまうし、ハンガー付け替えのペナルティなどもあって良い状態から別の良い状態への遷移を細かい遷移を繰り返して到達させることが難しいように感じました（雰囲気です、上手くできた人もいたかもです）。
焼きなましの方針
事前に各サイズについて担当範囲を固定させてしまえば、前から単純な貪欲を走らせることができるので、境界位置の決定をまずは焼きなましの遷移に入れました。
サイズの並び順については事前にサイズ間のペナルティの和が最も小さくなるように計算しておくとして、色の順序（複数置けるときの優先順位）も大切なので焼きなましの遷移に入れます。
後は、サイズの並び順は決まっていますが、逆順にしたりスタート位置をシフトすることはできるので、これも焼きなましの遷移に加えます。
細かい遷移の焼きなましと比べて局所解に陥りやすいので、ベストの記録よりも閾値（温度の定数倍に）以上悪化したら状態をベストの時のものに矯正する処理も加えました。
貪欲法
色の順序と色の境界、サイズの並び順が決まったらそれに従って貪欲法呼ぶことになるのでそれの中身です。
深読みとかを始めてしまうと、なんで焼きなまししてるのってことになるので、基本的に置けるものを前から順に置いていく貪欲なのですが、計算量を悪化させないでできるだけ工夫をしたいです。
具体的には、残りが少ない製品に関しては少し境界を突破しても置きたくなるので、どのような条件下でどれぐらいなら境界を突破しても良いかという処理を書きました（この辺りがa/bの比率に依存するようにしています）。
また、通過するときにハンガー回収するかどうかもa/bの比率に応じて変えるようにしています。
毎回全部を再計算していて、大体5万回ぐらいこの貪欲法が回っていました。
後処理
境界は最初に固定してしまうのですが、途中から境界を変更したほうがいい場合もあろうということで、ベストな解に対して途中から境界を少し変更して貪欲を走らせて改善したらそちらに置き換えるという処理を加えました。
そこまで大きな差はないですが、改善はしました。
後は以下の図のような置き換えもしました、単純にハンガーの数が少なくなったり使えるハンガーの数が多くなるのでお得です。
後は余白をなくすように後半部分をずらせるならずらすという処理も書きました。
反省点
パラメータ調整がかなり雑になってしまいました。
手元100ケースでやりくりしてましたが、回すたびに平均スコアが500とかブレて大変でした。
マラソンマッチに参加してた時のようにちゃんと鯖を借りて回さないとなと思いました。
