トヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026）

　56位。短期ヒューリスティックとしては悪くない順位なのだけど、もっと上にいけたはずなので悔しい。

コンテストへのリンク

コンテスト後のツイート

トヨタ自動車プログラミングコンテスト2023#6（AtCoder Heuristic Contest 026）
・一番小さい値を探すB[x][y]とする
・B[x][y+1:]で最も小さい値を探し、さらに……とし、それらの一つ上からを取り除き、他の列のうち、最小値の値が最も大きい場所へうつす。
この繰り返しで答えを構築し、焼きなまし

— titia (@titia_til) November 5, 2023

　本当に上位の解法は、「各山ごとにソートする」だったようだ。これは全く頭に上らなかったわけではないけど、あまり検討しなかったから仕方ない。

　自分の方針でももっと上位にいけた、というのが悔しい。

　まず、RUSTに直すところ。

これ、continueとすべきところ二か所がreturnになっていたのが原因でした。何故……。
それを提出しても7点しか上がらなかった（順位変わらず）ので、RUSTに書き換えたら上がるかも、と思ったのが間違いですね。
もっと良い方針がないか考え直すべきでした。

— titia (@titia_til) November 5, 2023

　エラーメッセージもないのに、実行しても何の出力も返ってこないので不思議に思っていたのだが、こんなミスをしていた。

　いやー。くだらないミスなんだけど、意外と気付きにくいか？　どうしたら気付けたのかなぁ。

　ただ、本質はもう一つの方です。

　ツイートの「焼きなまし」における遷移は、「x以上を山yに移す」を「x以上を別のランダムな山rに移す」に変更するというのだけ行っている。その後、スコア計算を愚直に行い、改善されていたら採用、もしくは、焼きなましの条件式を満たしていたら採用、としている。

　その条件式が間違っていた。

AHC、焼きなましの確率の式が間違っていた（exp(deltaScore / temp)でなくexp(deltaScore) / tempにしていた）ことに気付き、直したら1401325点（本番27位相当）、PyPyのままでも1400088（33位相当）出た。
コピペすれば良いのになぜこんなミスを……。
本番中に14に乗せられたはずと思うと悔しいね。

— titia (@titia_til) November 5, 2023

　なぜこんなミスを……。

　思い返すと、まずPythonで山登りを書いて、焼きなましに直す際、RUSTに直そうかな、と思ってちょっとだけ書き、「いや、もし間に合わなかったら嫌だからPythonのままで改善するか試そう」と思ってPythonでも焼きなましを書いたんだよね。

　そのとき、RUSTの焼きなましの式を見ながら書いたから、コピペでなくちょっと自分で直す必要が生じて、それで間違えたのだろう。

　その後、そのPythonの式を見てRUSTに直したから、間違いがそのまま残ってしまった、と。

　とはいえ、焼きなましの意味を理解していればこんなミスはしないはずですよねー。