ヤマト運輸プログラミングコンテスト2019
https://atcoder.jp/contests/kuronekoyamato-contest2019 に参加した。登録してないと問題文が読めないみたいですが。
問題1
クエリ数がまあまあ多いので全点対間最短距離だと思い、有向グラフを作って Warshall-Floyd をした。頂点数 2000 ぐらいにしかならなくて時間が 10 sec あるので実装が楽な Warshall-Floyd でやったけど、余分な辺を作らなければたぶん辺数が 10000 にもならないと思うので Dijkstra を頂点数回やったほうが速そう。
車両と台車で同じグラフを使おうとすると頂点を同一視していいかどうかとかの区別が面倒なので、二つ別々に作ったほうが楽だった。「辺を張る」と書いてるところは、Warshall-Floyd なら単に距離行列に値を書き込むだけでよい。
- 車両用のグラフ: 各道について、両端点に対応する頂点を作る。道は順方向と逆方向を区別して、それぞれ別々に作る。各駐車可能箇所にも対応する頂点を作る。同じ道の上にある頂点（駐車場所と端点）間にその間の距離に等しい長さの辺を張る（向きに注意）。さらに各交差点について、進入可能な端点の組み合わせすべてについて、長さ 0 の辺を張る。
- 台車用のグラフ: 道の向きを区別しないことと配達先も頂点にする以外は車両と同じ。辺もほぼ同様だが、交差点ではそこへ合流しているすべての道の端点の間に長さ 0 の辺を張る。
たぶんテストケースにひとつだけ交差点に駐車できるケースが含まれていて、これの処理を間違えて WA をもらった人がたくさんいそうだと思った（もらった）。
問題2
貪欲 + DP
配る順番を固定すると DP で最適経路が求まる。dp(i, p, k) = 「i 番目まで配って車が p にいて台車に荷物が k 個乗ってる状態になる最短の時間」とすると、O(荷物数 * (駐車場所数 * 台車容量)^2) 時間でできる。ということは、安直に考えると配る順番をうまく見つければよいことになる。
配る順番は、短い経路を見つけたいのだから直感的には短そうなハミルトンパスを探せばよさそう（ただし台車の容量とかの制約があるので最短のハミルトンパスが最適解になるとは限らない）。なのでそれっぽいヒューリスティクスを調べてみたら、一番近いところから訪問する貪欲法が一番簡単そうだったのでそれでやってみた。
ただし単純に距離だけ見て貪欲法をやると時間指定を考慮してないのでうまくいかないことがある。そこは指定時間で配達先を分類して別々にパスを作ってつなぐとかしてごまかす。始点によって実行可能解ができたりできなかったりするので、始点を全通り試す。それぞれの点から始めて貪欲法でパスを求めて、それに対して DP をして、最終的に一番よかったものを解として選ぶ。
とりあえずこれで 712 万点ぐらい出た。
bit DP
台車に荷物を乗せてそれらを配ってまた車のところに戻ってくるまでを一つのターンと考えることにする。
あるターンにおいて出発する駐車位置と配る荷物が決まっていて、荷物の個数が D のとき、そのターンの最適な行動はハミルトン閉路と同じ要領で bit DP をすれば O(2^D*D^2) で厳密解が出る。一ターンに配る荷物は10個までなので、これくらいの計算量なら問題なく最適解が求められる。そこでときどきこれをやってターンごとの経路の最適化をした。焼き鈍しの遷移の一部として書いていたけど、あらためてまとめを書いていたらこれは遷移とは性質が違う気がしてきたので、もっと別の扱い方があったかもしれない。
ちなみに荷物の個数や駐車場所が決まっていなくて D 個の荷物を配る最短時間を求める DP は、駐車場所の数を P, 台車の容量を K として O(2^D * (DPK)^2) になる（と思う）のであまり D を大きくできなくて、部分的にやるとしてもやや厳しいかなと思った。荷物12個で駐車場所固定とかだったらできるので二ターンまとめて最適化をちょっとだけやってみたけど、あまり効果がなさそうだったので没にした。
山登り・焼き鈍しの遷移について
列を変化させるというとすぐ思いつきそうなのが次の二つ。一つめは TSP とかでよくある 2-opt と同じだと思う。
- 区間を選んでその範囲の順序を反転する
- ひとつ要素を取り除いて別の場所に挿入する
二つの要素の swap も一瞬考えたけど試さなかった。ランダムな swap だとあまり効きそうになかったから検討しなかったけど、よさそうな組を探して swap すれば効果はあったかもしれない。
これに加えて上に書いた bit DP もときどきやってみた。
このあたりの近傍を使って山登りをしたら 739 万ぐらいまで、焼き鈍しと諸々の高速化や温度調整をやっていたら 746 ぐらいまで上がった。さらに初期解を改善したり、よさそうな遷移を選ぶ確率が高くなるようにしたりして 750 ぐらい。
あるとき10000点の境界が壁になってるのが問題であることに気付く。例えば 800010 点とかの時間ぎりぎりで最後の荷物を配達する経路を見つけたときに、ここからスコアが上がる近傍がほとんどないみたいな状態になる場合があって、下手にここにはまると遷移がほとんどできなくなって詰んでしまう。こういうときには一度790000点台(実際は790100点とかになる)に下がることを許容したい。
これに気付くとまずは温度を上げたい気持ちになるのだが、-10000点をたまに受け入れるような温度にすると小さなスコアの低下はほぼ必ず受け入れることになってしまう。そんなことをするのもどうかと思ったので、温度は上げないで、普通の判定とは別に-10000点ぐらいだった場合に遷移するかどうかの判定をアドホックに追加した。
焼き鈍しの高速化について
DP がけっこう時間を食うので高速化が必須、なのだが結局それほど頭のいいことはしてない。
- 差分計算。遷移で変えたところより手前は計算し直さなくてよい。
- DP の途中で時間がかかりすぎてそうな状態からの遷移は考慮しないようにする。
- 焼き鈍しの途中で現れる解の中で使われる駐車箇所は、手元でテストした限り全駐車箇所の一部だけだったので、、最初の 20 秒の間にどれが使われたか記録しておき、残り 40 秒は使われなかったものを無視して DP する。
これで数倍から10倍くらいにはなっていそう（いろいろ変更しながら最終的に上のようになった、という感じなので、あまり正確な比較はできてない）。DP の枝刈りをどこまでやるかはけっこう微妙なところかもしれない。
評価関数について
今回あまりうまい評価関数を思いつかなかったのだけど、この問題のスコア関数はそのままだと焼き鈍しに向かない気がするので、本来はもっと力を入れるべきところだったかもしれない。
一応、配れなかった荷物についてもなんとなく惜しそうだったら点数が追加される感じにした。残りの荷物それぞれについてどれくらい時間オーバーするか計算して（正確に計算すると時間がかかるので単純に台車での移動時間と滞在時間を足していった）、オーバーする時間に対して指数関数的に小さくなる項をスコア関数に足した。
これにどの程度効果があったのかはわからないが、10000点ぶんぐらいは貢献しているかもしれない。手元でテストしたときはむしろ悪くなってるのではと思ったけど提出してみたら少なくとも悪くはなってなさそうだったから消さないでおいた。
もうちょっと真面目に検討するならまず怪しい気がするのが台車の容量を無視しているあたりで、単純に移動時間を足すよりももっと正しいやり方があったのかもしれない。DP を最後までやるのが数値的には一番正しく出るけど、そこまでやると正確に計算できるメリットよりも計算時間がかかりすぎるデメリットのほうが大きそう。
もっと細かい点では、時間の単位を 1/50 秒にしていたので（そうするとすべての時間が整数で計算できる）、本来のスコアの値それを 50 倍にしたものを使っていた。切り捨てが発生しないのでこのほうが精度がよさそうな感じがしてそうしたが、実際はどちらでも大差なさそう（焼き鈍しの遷移判定のときに若干の違いは出る）。
いろいろ
- 配達順序を焼き鈍す方針をとってみたが、これだと駐車位置のことはほとんど考えなくなるので楽な面もある一方で、せっかく使える情報を捨ててしまっていたようにも思える。
- 提出ごとに何を変更したか、スコアがどうだったかを見やすく整理できる仕組みがあるとよさそう。
- generator を書いたのでけっこう自分で生成したテストケースを使ってテストしたが、細かい変更に対してスコアが改善するかどうかは手元でのテスト結果と提出結果で一致しないこともよくあった。
- visualizer も書こうとしたけど見やすい表示方法を思いつかなくて使えるものができなかった。どう表示するのがよかったんだろう。絵にこだわらないでテキストでもいいからいろいろ解の情報を書き出したり、手動で解をちょっと変更してスコアがどうなるか観察できるようにしておくとよかったかもしれない。
