あるとき10000点の境界が壁になってるのが問題であることに気付く。点とかの時間ぎりぎりで最後の荷物を配達する経路を見つけたときに、ここからスコアが上がる近傍がほとんどないみたいな状態になる場合があって、下手にここにはまると遷移がほとんどできなくなって詰んでしまう。いうときには一度790000点台(実際は790100点とかになる)に下がることを許容したい。これに気付くとまずは温度を上げたい気持ちになるのだが、-10000点をたまに受け入れるような温度にすると小さなスコアの低下はほぼ必ず受け入れることになってしまう。そんなことをするのもどうかと思ったので、温度は上げないで、普通の判定とは別に-10000点ぐらいだった場合に遷移するかどうかの判定をアドホックに追加した。時間を食うので高速化が必須、なのだが結局それほど頭のいいことはしてない。遷移で変えたところより手前は計算し直さなくてよい。途中で時間がかかりすぎてそうな状態からの遷移は考慮しないようにする。これで数倍から10倍くらいにはなっていそう(いろいろ変更しながら最終的に上のようになった、という感じなので、あまり正確な比較はできてない)。枝刈りをどこまでやるかはけっこう微妙なところかもしれない。評価関数について今回あまりうまい評価関数を思いつかなかったのだけど、この問題のスコア関数はそのままだと焼き鈍しに向かない気がするので、本来はもっと力を入れるべきところだったかもしれない。一応、配れなかった荷物についてもなんとなく惜しそうだったら点数が追加される感じにした。残りの荷物それぞれについてどれくらい時間オーバーするか計算して(正確に計算すると時間がかかるので単純に台車での移動時間と滞在時間を足していった)、オーバーする時間に対して指数関数的に小さくなる項をスコア関数に足した。これにどの程度効果があったのかはわからないが、10000点ぶんぐらいは貢献しているかもしれない。手元でテストしたときはむしろ悪くなってるのではと思ったけど提出してみたら少なくとも悪くはなってなさそうだったから消さないでおいた。真面目に検討するならまず怪しい気がするのが台車の容量を無視しているあたりで、単純に移動時間を足すよりももっと正しいやり方があったのかもしれない。最後までやるのが数値的には一番正しく出るけど、そこまでやると正確に計算できるメリットよりも計算時間がかかりすぎるデメリットのほうが大きそう。倍にしたものを使っていた。切り捨てが発生しないのでこのほうが精度がよさそうな感じがしてそうしたが、実際はどちらでも大差なさそう(焼き鈍しの遷移判定のときに若干の違いは出る)。配達順序を焼き鈍す方針をとってみたが、これだと駐車位置のことはほとんど考えなくなるので楽な面もある一方で、せっかく使える情報を捨ててしまっていたようにも思える。提出ごとに何を変更したか、スコアがどうだったかを見やすく整理できる仕組みがあるとよさそう。書いたのでけっこう自分で生成したテストケースを使ってテストしたが、細かい変更に対してスコアが改善するかどうかは手元でのテスト結果と提出結果で一致しないこともよくあった。書こうとしたけど見やすい表示方法を思いつかなくて使えるものができなかった。表示するのがよかったんだろう。絵にこだわらないでテキストでもいいからいろいろ解の情報を書き出したり、手動で解をちょっと変更してスコアがどうなるか観察できるようにしておくとよかったかもしれない。プログラミングコンテストに参加しました。107マラソンマッチ始めてみました。