画像は AtCoder Marathon Rating History より
AHC 001〜005 の5回連続で1桁順位を取ってレーティング（β）が2800を超えました。
各コンテストでどういったことを考えて方針を定めていったのかを書きます。
AHC001 5位（長期）
焼きなませるので焼きなます。
賢く構築するみたいなのがあるかもしれないけど、どっちにしろ最後には焼きなますし、それに勝てるような構築パターンがあるともあまり思えない。
焼きなまし、汎用的なメタヒューリスティクスとして強すぎて、よほど近傍の計算が重くて数千回しかイテレーション回せないとかじゃない限りとりあえず選んじゃう。
長方形の数も少なくてたくさんイテレーション回るから、変に自分で賢く考えようとするよりは計算パワーに任せた方が良い。計算パワーが正しい方向に向かうようにすることを考えていく。
焼きなましではできるだけ小さい変化の（評価関数がなだらかになる）近傍を取るというのが基本なのだけど、この問題で「ひとつの長方形を選んで、辺の位置を1ずらす」をやってもほとんど良い方向の遷移にならないのは、ビジュアライザを見てイメージすればわかる。
ひとつの長方形を縮めて空いたスペースに他の長方形を広げる、といった事をやりたい、のでそれを実装する。
ルールベースで「L字型に接している部分を…」みたいにすることもできるかもしれないが、それだと実装が大変なことになりそうなので「一部を破壊して再構築」の方針でやる。こういう近傍はTCO20 Finalでもやった。
壊すフェーズの後の広げるフェーズはgreedyにやりたいが、どういう方針で置くのが妥当かというと…
基本良い解では長方形がぎゅうぎゅうになるので、ひとつずつ長方形を取って、縦か横にできるだけ広げる、とする。
ただし多様性も確保するため、常にできるだけ広げるのではなく、一定確率でランダムな位置までしか広げない、とする。
長方形を後から縮めるのは簡単にできるので、スコア関数をいじって目的の面積以上の場合は目的面積ちょうどと同じ評価とした。これもこの近傍の妥当性に寄与している。
AHC002 3位（短期）
とにかく詰まないようにできるだけ盤面全体を回れるようにすることが一番大切。そうすればスコアも勝手についてくる。
適当に経路を取って一部を破壊してつなぎ直し、というのが典型的な考え方としてまず見えるが、この問題の制約の下でつなぎ直して経路を育てていくのがどれくらいできるものなのか、やってみないとわからない。
実装めんどいなーと思って、まずはgreedyに伸ばしていくのを書いてしまった。各方向に1歩進んだ後、モンテカルロ的にランダムウォークして最大何歩まででいけるかを求めて、それが最大な方向に動く。
そうすれば即詰みは回避できる。
しかし試してみたらかなり弱い。ビジュアライザを見ると盤面全体を大局的に見れてないから中期的に詰んでしまってるのだと思い、盤面の上の方を優先するとか開始位置に近い所を優先するとかいろいろやったけどだめ（こういう評価の方法も典型感はある）。
ここまでで1時間くらいで、時間的にもこれ以上引っ張ると他の方針が実装間に合わなくなるのでこの辺で転換して、観念して最初の破壊・つなぎ直し遷移を実装した。したら強かった。
遷移は、ランダムウォークして切ったところまでたどり着けたら候補とする、だったけどもう少し工夫の余地はあったっぽい。
たぶん多くのケースで元々の経路と同じになっちゃってるし。
AHC003 9位（長期）
インタラクティブ問題が多腕バンディット問題っぽくなるのはよくあることで。
通った経路の情報をフィードバックしつつ、未知の辺を使って情報を集めていく感じにしかならんなあとなった。
- 未知の辺を使いやすくなるように序盤は辺を使った回数に応じたボーナスを付ける
- フィードバックの計算を逐次更新ではなくて頻繁に履歴の情報を使って最初からやり直す
- これは改善するのが非自明だけどやってみると良い結果になった
- 隣接する辺に情報を伝播させるようスムージングする
といったアドホックな調整に終始する感じだった。
あまり時間がなかったという事情もあるが、もっとデータサイエンス力があれば、モデルを作ってそのパラメタを最適化…みたいなしっかりした方針でやれたのだろう。
AHC004 7位（短期）
すべての基本は貪欲なので、わかりやすい貪欲を考えると…とりあえず縦に揃えるのを無視して横1行ずつ貪欲に揃えていけばどんな悪くても50%は超えるだろう。60%強はいくのでは？ と見積もった。
ただ完全解が達成できるものかはよくわからず、最初は完全解を出せるかもしれない方針で行ってみる。
各文字列を盤面内に撒いて、その位置を変更すると言う遷移で焼きなまし。各セルの文字の分布がひとつに集中している方が良い。
そんなに筋の良い解法では無さそう感はあったけど、計算パワーを信じてみた。が全くダメだった。
「各セルの文字の分布がひとつに集中している」の評価も難しくて、単純にやるとそのセルを使う文字列が1つだけしか存在しなくて1/1で完全に集中してるとみなされる、というケースが最強になってしまう
6時間中1.5時間くらい経ったので、完全解は諦めて1行ずつ貪欲の方向に移行する。
計算時間には余裕があるので貪欲というかビームサーチ。文字列ひとつ使うのを1ステップにすると、文字列をひとつ置いたときに盤面がどこまで埋まっているかが統一されないのをどう評価するかとかいろいろ大変なので、1行分を作るというのを1ステップとした。1行分作る中にランダム性を持たせて多様性を出す。
縦側を完全に捨てているのをなんとかしたいなと思い、縦1列分だけ先に作ってその後横を1行ずつやるようにしたらけっこう上がった。1列じゃなくて2列にしたらさらに良かったのでそれで。
横を作るときは先頭が固定されていてもそこまでスコアに影響はなく、縦で稼げてる分有利になるということでしょう。
文字列を先頭2文字で分類して保持したことがけっこう高速化に効いてそうだった。
完全解解法は、短期の時間の中でやるのは自分には無理っぽい…。
短期AHCは企業コン予選を想定してtop10に入れる確率最大化を目指しているので、まあ良いでしょう。
AHC005 8位（短期）
全マスを使った経路と捉えると難しいが、交差点間を移動する問題と考えると何も犠牲にすることなく問題空間が大幅に小さくなる。
そして交差点をいくつか選んだらTSPすればよい。
重要な点を抽出してTSPするというのはまあ典型ではある。この問題は短期にしては実装が重かったが…。
使う交差点の集合というシンプルな情報で解を表現できるので、これをちょっといじってスコアを再計算することで山登りできる。
思ったよりもこの交差点の選択でのスコアの変化が大きく、TSP部分は最近傍法だけで済ませる形にした。最後だけちょっと2-optをかける。
実行のたびのブレが大きい感じだったので多スタートをした。ビジュアライザで眺めてみても、よい局所解同士が遠いところにありそうだし。
最後のほうで、交差点ベースじゃなくて辺ベースで情報を持った方が実装楽だったかなと思った（書き直す時間はもうなかった）けど、スコア的にもその方が良かったみたい。
たしかに辿るべきは交差点ではなくて辺だからか。
