Hack to The Future 2019 Qualifier
マラソンマッチは8時間もあるので、途中で食事をとることになります。 「コンテスト中に休憩をしてごはんを食べるというのはなかなか楽しそうだなあ」と思い、参加しました（謎）
予習もしくは予備知識
ツカモさんの記事を何となく読んでいました。 qiita.com
あと、山登り法とか焼きなまし法そのものは書いたことがなかったのですが、統計力学の勉強でイジング模型のMCMC（マルコフ連鎖モンテカルロ法）を書いたことがあって、あと量子アニーリングなるものについて友達に教わったことがあったりして、お気持ちは少しわかる程度の予備知識がありました。マラソンマッチは初めてだけど、本当に初めてではないみたいな感じです。
競プロしてるけど統計物理知らない（特に若い）競プロer向けに↑の話を紹介すると、統計力学のシミュレーションのMCMCでは温度を固定して、コスト的に損をする状態変化も一定確率で許すようなマルコフ連鎖を作ります。ここでいうコストは物理だとエネルギーに置き換わります（低いほうがコストは得という扱いです）。マラソンの焼きなまし法だとここで温度を下げていくことでエネルギー的に損をする遷移を許さないようにしていくことで最適解を目指します。一方、統計力学では温度T>0のときの分布そのものにも興味があります。どういうことかというと、Tを固定して変化していく状態に沿って物理量の平均や分散を計算することで比熱だとか磁化率だとかが計算出来ちゃったりします。そして温度を変えながらそれらを繰り返すことで、強磁性・常磁性相転移、つまり温度の低い鉄は磁石になるけどある温度を超えると磁石じゃなくなるという現象（の本質的モデル）をシミュレーションで再現できちゃいます。しかも実装は簡単ですから、興味のある方はやってみるとよいとおもいます。以上は知ってることだけざっくり書いたけど、ほかにもいろいろ競プロerのみなさまにとっても興味を惹かれることがあるはずです（適当）
最初の一歩
First ACを狙って問題文をろくに読まずに全部.で出すなどしました。壁がないのでWA。
制約を読んでからいったんPython3で80000なんちゃら点の壁＋.を提出。 最後はJavaで書こうと思っていたので後々直すことを想定しつつ、やはりツカモさんブログのコード例を参考にしながら...だけの解を出すコードをJavaで書く。 参考にするといいつつちゃんと参考にできておらず、static変数を無数に使うことになる。マラソンの場合何度も書き直したりモジュールの一部を置き換えたりすることがあるから、短時間のアルゴよりは書き方を考えないといけないですね。
拙速編
次にシミュレーターを書く。愚直にロボットを動かし、カウントを増やし、最後に数えるというもの。けっこう重い処理なのはわかっていたけど改善しようとするのは後回しにした、というか考えたくなかった。自分の実力では4時間かけてようやくテストできるようになりそしてバグるというのがとてもありそうです。
そこでまず愚直に書いた。書いた後、自分の書いたシミュレーターにバグはないという信念のもと（謎）山登り法を実装する。スコアが下がる。いや、下がるわけないでしょ。シミュレーターをなぜすぐにテストしなかったのか？山登り法を一刻も早く書いてみたかったからですね。今回1度書いて満足したので次からは一歩一歩テストしながら進むことができるでしょう。
この時点でそこそこ疲れ始めており、シミュレーターのデバッグか、嫌だなあ。。。などと思い始めていた。まあやるしかないのですが。このあたりでビジュアライザーの存在を思い出す。最初よくわからずビジュアライザーにコードをサブミットし、WA。このへんで2時間経っており、デバッグ嫌だなあなどと思っている時点で休憩のしどきであることにようやく気付き、コンビニに出かけてココアとオレンジジュースを買ってくる。往復10分ほど歩けたので帰ってからやることを整理することができた。
シミュレータデバッグ編
ビジュアライザーの使い方を理解してビジュアライズするとまずロボットのカウントからして間違っている（やはりね）。そもそもLマスRマスの仕様が自分の理解とあっているか不安になった（S命令だったら実行しないという解釈もあり得るのでは？みたいな。）。質問投げようかとも思ったんだけど、ビジュアライザーのページのJavaScriptにシミュレーターが書いてあって、それを読んだ結果自分の理解があってるってわかりました。
そこがクリアできたので気を取り直して自分のコードを読み直していたのですがどこも間違っておらず（だからまちがってるんだって）、書き直したほうが早いという結論になった。書き直しにあたってはせっかくなのでビジュアライザーのJavaScriptを参考にさせていただいた。ビジュアライザーのコード読みやすかったです、ありがとうございます（読んだ人どれくらいいるんでしょう）。
そんなこんなで再実装が終わり、ビジュアライザーを使ってシミュレータが正しそうなことを確認できたので、すでに拙速実装していた山登り法を実行すると、その時点で11万点を超えることができ、満足した。この時点で18時を回っており、夕食を取ることにした。
焼きなましからの撤退編
夕食後は焼きなまし法を実装した。そうすべきだと思ったからではなくて、書いてみたかっただけですね。実際、シミュレーターが愚直であるため山登りのループ回数が1300回程度しかなく、そもそも局所最適に至れているかも怪しいわけで、焼きなましを試す段階ではなかったのでしょう。でもまあ、書いてみたかったので。。。
次回同じ状況でやろうと思うのは、ローカルで実行時間を30秒とかにして山登りの解が改善するかどうかの実験です。（これはうさぎさんのブログで学んだことです）改善しなければ少なくとも局所最適になっているので、そこを脱出するために焼きなます価値がありますが、今回の僕の場合は山登りしきれていない（と思う）ので、シミュレーターの最適化をすべきだったということだとおもいます。
これくらい論理的に考えて何をすべきかわかっていればさすがにシミュレーター高速化を試みたと思うのですが、状況がよくわかっていないとなんとなく自分が楽にやれそうなことややってみたいことをやってしまいますね。
というわけで、焼きなまし法で目立った改善はできず、時間をギリギリまで伸ばすなどして数千点の改善にとどまりました。この辺でやれることが尽きたので、風呂に入って撤退しました。撤退って決めても何か集中できることをしないと気持ちが撤退しきれないので、ゲームをして解説放送を待つことにしました。
まとめ
- 山登り、登り切っていますか？
- 今書いたところ、テストしましたか？
- 今すぐ休憩すべきじゃないですか？
