第5回 Asprova プログラミングコンテスト
https://atcoder.jp/contests/asprocon5 に参加しました。
第4回同様焼き鈍しじゃないことをしたいなーと思いながら考えたんですが、結局焼き鈍しをしました。でも焼き鈍し部分にはまだだいぶ改善の余地がありそうな状態だったので（具体的にどこに改善の余地があるかの検討すらできていない）、たぶんアイデアがよかったのだと思います。
オーダをバッチに分けて一列に並べて先頭から順番に割り付ける貪欲法を書いて、バッチの分け方と並べ方を焼き鈍しました。一つのバッチは必ず同じ資源を割り付けるようにします。こうすると作業の間に隙間ができにくくなると同時に、実質的なオーダ数を減らすことができて処理が高速化になります（という証拠をちゃんと持っているわけではないけど、スコアがよかったのでたぶんそういうことだと予想）。
最初にやったこと
とりあえず generator とサンプルのソースを読む。問題文に明示的に書かれていないこととか正しく理解しているかどうか気になったことをいくつか確認する。
- item, resource を決めると対応する role は（存在すれば）一意に決まる
- item, role を決めても resource は一意に決まらない
- 特に、多くの場合は item ごとに main resource が複数ある（サンプルコードを見ると一つしかないような処理をしているけど単に決め打ちしているだけ）
- order の profit は q と item の profit で定まる
- 段取りペナルティは副資源の選び方に依存しないで決まる
あとテストケースを生成するスクリプトを書いたり、generator を少し改変したりした（A=1000 のときにペナルティ係数を強制的に1000にする処理を入れただけ）。
output_checker のエラーメッセージをもっと詳しくする作業をやっておくとよかったかもしれないと後で思った。毎回同じことを思っているけど、毎回原因のわからないバグが発生したらその都度必要そうな情報を出力するように書き換えて何とかしている。
次に入力を読むコードを書いてみた。自分でこういう作業をすると問題の意味が少しわかってくるので、じゃあどういう風にしたらいいだろうかということをいろいろ考え始める。（とりあえず自明な貪欲法でいいので最初に自分で書いたほうが理解が早かったかもしれない）
あまりよさそうな方針を思いつかないので、前回までに何をやったか思い出してみた。以下前回のメモの一部。
- 注文と設備の組を全通り試して、割り付けたときにその前にできる隙間時間と段取り時間と終了時刻の和が最小になる組を次に割り付ける貪欲
- 遅延がないときに penalty の計算をしない（浮動小数点数の演算があるのでけっこう違いが出る）
- スコア計算式の粗利のところは全注文の pr の総和が足されるだけなので、入力を読んだときに総和を覚えておいて、あとで足せばよい
- a はペナルティ計算のときしか使わなくて必ず pr/a の形で出てくるので、はじめから pr/a だけ覚えておけばよい
前回との大きな違いになりそうなのが資源が複数あることで、どの資源に割り付けるかの組み合わせが場合によっては膨大なのでそこを工夫する必要がある。例えば主資源だけ全部試して、副資源は貪欲に決めるとかだろうか？あるいは組み合わせではなく役割ごとに全部貪欲に決めるとか。
とりあえず貪欲
とりあえず何をしたらいいかよくわからないので、注文を開始時刻でソートして貪欲に割り付けてみる。サンプルコードとあまり変わらないけど、全資源を見て一番早くなるように割り付ける。
それだけだとあまりよくなくて、単純に最早開始時刻でソートすると同じ品目の注文がばらばらに割り付けられてしまう。そこで最早開始時刻を適当な値(32768とか)で割った商でソートして、商が同じなら品目番号でソート、とかをいろいろするともっとよくなって手元で生成したテストケースで1960から1970ぐらい出る。
よさそうなのを提出してみたら 1994 が出ていた。手元で試したスコアよりだいぶよいので、もしかしたらある程度いいスコアが出るテストケースが選択されているのかもしれない。システムテストもそうなのかが気になり始める。
そういえばスコア計算をするコード書いてないなと気付いたけどまだ焼き鈍しを書く段階ではない感じなので保留にする。
貪欲法の難しさ
このあたりで気付いた、というか思い出したことなのだけど、途中までの計画ができているときに、次にどの注文をどこに割り付けるといい感じになるかということを評価するのがその時点ではかなり難しい。
余談だけどこれはスケジューリングに固有の話ではなくて、例えば囲碁とかでどの手を打つとその後に有利になるかを評価するのが難しいのと似ていると思う。なので逆に考えると、囲碁とかでこれをどう克服しているかというのが参考になるのではないか、ということは前から思っていて、第4回のときはモンテカルロ木探索みたいなことができないかということを少し考えたのだけど、あんまりうまくいかなかった（素人がちょっと試してみたけどだめだったという話なので、プロがやるともっといろいろやりようがあるのかもしれない）。
とりあえず思いつくこととして、どの注文を割り付けるかも決め打ちしないで適当な評価に基づいてやってみたらどうなるだろうかというのがあるので、それを試すことにした。擬似コードで書くとこんな感じ。
score = -1
next_o = -1
for each o in order:
for each m in main_resource[o]:
temp = assign_and_eval(m, o)
if temp > score:
score = temp
next_o = o割り付けの評価関数に使えそうな要素として思いつくものは、隙間時間・終了時間・段取り時間・遅延ペナルティ（係数の大きさも？）あたりがある。
ちょっと問題なのが遅延ペナルティの扱いで、早く終わる割り付けがあるのにわざわざ遅くなるところに割り付けたくはないので、その観点からは遅延ペナルティをマイナス評価にしたい。一方で、単純にそうしてしまうとどこに割り付けても遅れるような状態の注文がずっと放置されてしまう可能性がある。だからもしかすると遅延ペナルティの発生している注文は逆に優先的に割り付けられるべきなのかもしれない。要するに、遅延の発生をプラスに評価するのかマイナスに評価するのかというジレンマがある。*1
たぶん、割り付けのスコアへの寄与という意味での評価と、割り付けの優先度とは異なる概念なのだろう。それを同じスコアで測ろうとしているのがよくないのだ。でも、仮に別々のスコアを考えたとして、それを使ってどう計画も組み立てるのか？というのがそんなに自明ではない。
そんなようなことを考えながら、遅延ペナルティをプラスに評価して遅延するほど優先して割り付けるようにしたらスコアが上がったりした。
ただ問題があって、次にどの注文の割り付け先を決めかまで毎回全探索するようにしたので、計算時間がかかりすぎている。手元のマシン（AtCoder のジャッジサーバと同じくらいの実行速度）で大きいケースが 6sec とかかかるので TLE になる。
そこでとりあえず実行時間を測りながらあとどれくらいかかるかを推測して、TLE しそうなら探索範囲を狭めるとかしてむりやり対応してみた。
それから少し細かいこととして、後ろに割り付けるだけではなくてある時間帯に暇になっている資源があるときはその隙間に新しく作業を割り付けたい。これを主資源に対してやろうとすると段取り時間の変更でいろんなところに影響が出て大変（第2回のときはそれをちゃんと書いたけど）なのだけど、副資源だけなら後ろに波及しないのでやってみた。ちなみに後で焼き鈍しをやるときはこれをやらないほうが高速で試行回数が稼げてよさそうだったんだけど、一応両方提出しておいたところ最終的に最高スコアを出したのは隙間にも割り付ける版だった。テストケース依存でどちらがいいかが変わりそうなので（ちょっと見た感じだと大きい入力に対しては試行回数を稼ぐほうがいいようだ）、正しく使い分けるようにしたらもっとスコア上がったかもしれない。
ここまでのことを書いて提出してみたら 1997 になった。これ以上の本質的な改善はなかなか思いつかなかったのでちょっと別の何かをしないといけないなと思って考える。
上述のように、途中までの割り付けが与えられたとき、それが残りの割り付けまで考えたときにいい状態なのかどうかを評価するのが難しい。これが本質的な困難な気がして、これは何らかのヒューリスティクスで簡単に乗り越えられるようなものでもない感じがした。こういうときは計算機の力に任せていろいろ試していいやつを選んでいくのがよくて、それはお馴染みの焼き鈍しではないかという気持ちになる。
このあたりの考察をしていたのが1/3の午後。そろそろ残り時間が気になってくる。
バッチ化
副資源がボトルネックのとき、主資源から決めるやり方だと隙間が大量にできてしまう。特に副資源に異なる品目が交互に割り付く形になりがちで、きれいに詰め込まれない。そのせいで副資源に空いているところが見つからなくて後回しになる注文が出てくる。こういう状況がスコアを下げていそうなので、なるべく同じ品目の注文を連続するようにまとめて割り付けることで隙間ができにくくしたい。
これを解決できるかもしれない方法として、同じ品目に対するいくつかの注文をひとまとめにして、まとまりごとに順番に割り付けていったらどうかということを思いついた。ここではひとまとまりの注文群のことをバッチを呼ぶことにする（コンテスト中に提出したコードでは cluster と呼んでいたけどバッチのほうが近い気がする）。
とりあえず注文をバッチに分ける処理を適当に書いてみた。バッチは注文の列で、注文全体はバッチの列として保持される。この列の先頭から順番に貪欲に割り付ける。バッチの順番はこれまでと同じように最早開始時刻でソートしてやって、これと今までと同じようにして貪欲に割り付けてみたら、ただの貪欲よりもかなりよくなった。
ただビジュアライザを見てみると、クラスタサイズが大きいときは二つに分割して手分けしたほうが遅延が小さくなるケースがある。どういうときにどうすればいいかを探りながらヒューリスティクスをコーディングするのは大変そうなので、こういうところの最適化は焼き鈍しが強いのかもしれない。
とりあえずバッチ化がどれくらいの効果を持つのかを確認するために、バッチ化したあと単純な貪欲法をやるコードを提出してみたら 199820474638 になった。実行時間 8 msec でこのスコアだったので、焼き鈍しがうまくいけばだいぶスコアが伸びる気がしてくる。
焼き鈍しをする
3通りの遷移をする焼き鈍しを書いた。
- ランダムに選んだ二つのバッチの順序を swap
- ランダムに選んだバッチと、その次に現れる同じ品目のバッチを一つにまとめる
- ランダムに選んだバッチをランダムな位置で二つに分ける
とりあえず動くものを書いてみたらスコアはかなり上がるようだった。実行時間を伸ばしたらまだ上がるので、高速化がある程度は効きそうだということで、差分計算ができるようにしてみたり割り付けの計算中にペナルティが大きくなったら途中で打ち切ってみたり、データ構造を変えて（サイズが小さいから定数倍の違いが効いて map で O(log N) の処理より vector で O(N) のほうが速いとか）高速化を図ってみたりした。
最後に温度調整もしたのだけど、これはだいぶ目測を誤って低めの範囲で探索してしまって、試した中で一番温度の高いものが最高スコアだった。もっと高い温度にしたらスコアがよくなったかもしれない。しかも時間がなくて温度調整をしながら別のマシンでコードを書き換えていたので本当に適切な温度が選べている可能性は低い。
他の最適化として、結局あまり真面目にやらなかったけど遅延している部分のペナルティ最小化も考えた。隙間のない連続した同品目の割り付けについては a * q / pr の昇順にするだけだから O(NlogN) でできる。ただし、どう並べ換えても全注文で遅延が発生し、かつどう並べ換えても最早開始時刻に違反しないというような条件が必要なはずで*2、たまにこの条件が破られることがあるのでちょっとめんどくさい。
あとコンテスト期間終了後に気付いたのだけど、バッチ中での注文の並べ替えも遷移に入れたほうがスコアが上がった。最初に焼き鈍しを書いたときはあまり効果がなかったように見えて没にしたけど、高速化して試行回数が増えることで状況が変わったのかもしれない。バッチ間の swap に比べるとスコアへの影響が少ないので、試行回数が少ないときは他の遷移のスコア変化に埋もれてしまっていたのが試行回数が増えることで見えるようになったとか？
