焼き払え！！皆解会002（AHC002バチャ）参戦記
はじめに
皆解会（AHCをみんなで解く会）とは、その名の通りAtCoder Heuristic Contest（AHC）の過去問を皆でワイワイ解くDiscordグループです。歯科医競プロerとして知られるainemさんが主催しています。
第2回となる今回は、AHC002（本来は4時間の短期個人戦コンテスト）を10日かけてチーム戦で解くバーチャルコンテスト（以下バチャと省略）でした。短期コンテストの問題をチームメイトたちと相談しながら長い時間をかけて解くので当たり前と言えば当たり前なのですが、全チームがバカ高いスコアを叩き出し大怪獣バトルの様相を呈していて非常に楽しかったです。
そんな激しい戦いの末に我がチーム「三尺秋水」は残念ながら最下位となってしまったのですが、ずっと憧れていた焼きなまし法を初めてマトモに使えたので、個人的には大満足のバチャとなりました。バチャくらいでわざわざ参戦記書くの！？というツッコミが聞こえてきそうですが、初めてちゃんと焼けた喜びの記録を残しておきたいので書いちゃいます。
さて、本題に入る前に一つ注意事項があります。本記事の趣旨は「初めて焼きなましできて嬉しい！！！！」ただそれだけです。焼きなまし法についての実用的な記事ではございません。ただの日記です。私の「嬉しい！！！！」という叫びをちょっと解像度上げて長ったらしい記事に仕立てただけです。実用性は期待しないでくださいね！！
Before Contest
まずはチーム決めです。30人の参加者が6チームに分けられます。今回のチーム決めはざっくり言うと「チーム内での議論が成立しやすいように、概ね実力が近い者同士で分ける」方式なので、チーム間での実力差がかなり出てしまいます。
我がチーム（チーム番号1番）は最弱です。青パフォ経験者が一人もいない唯一のチームとなりました。メンバーはスコティさん、がぶりえるさん、rinrionさん、jabeeさん、そして私です。
メンバーの次はチーム名決めです。我々が最弱であることを念頭に置いたチーム名にしたいですね。私が出した案は以下の通りです。
ポジティブ（下剋上）路線
ネガティブ（敗北の美学）路線
- テルモピュライ（少数のスパルタ軍が大国ペルシアを相手に善戦するも最終的に全滅した戦いの地）
- 落日燃ゆ（城山三郎の小説のタイトル。個人的には敗北の美学を感じます）
- 能島村上水軍（敗北の美学のカタマリです。城山三郎「秀吉と武吉」を読んでね）
- あしたのジョー（真っ白に燃え尽きたいよな）
- 八重樫（ボクサーの八重樫東から。めちゃ強かった頃のロマゴンを相手に勝てない戦いに挑み、美しく散りました）
えー、明らかにネガティブ路線の方が早口のオタクになってますね。ご察しの通り私は敗北の美学が大好きです。なんかカッコいいじゃん。
私としては「落日燃ゆ」が最推しだったのですが、最終的には多数決でスコティさんが提案した「三尺秋水」に決定しました。意味はググってください。めちゃくちゃカッコいいです。
全チームのメンバー表はこちら。どのチームも良い感じのチーム名とロゴですね。我ら「三尺秋水」と「ひよこ」の毛筆ロゴはainemさんのご友人に書いて頂きました。カッコいい！！
チーム名の議論を通して十分にアイスブレイクできたところで、12月2日、いよいよコンテスト開始です！！！！
1日目 12月2日（金）
所用で関東に行っていたので私は何もしていません。
2日目 12月3日（土）
同上
3日目 12月4日（日）
同上
4日目 12月5日（月）
週末に何もできないまま平日になっちゃいましたね。でも大丈夫です。何故なら先週ボルダリング中に落っこちて右足首を痛めてしまい長期休職中なので！！
私の仕事は山や海での肉体労働なので、ちょっとした怪我で仕事ができなくなって収入が消えます。今月の収入はほぼゼロになりました。貯金なんて一切無いですし、会社員ではなく社会保険にも入っていないので傷病手当金なども貰えません。マジで来月生きていけるのか！？非常に不安ですが、まあおかげでこのバチャに集中できるぜ！！！！！！！（ヤケクソ）
いざ戦闘開始！！まずはビジュアライザのマニュアルモードで遊びながら問題の雰囲気を掴みたいところ。しばらく遊んでみて思ったのは、目先の移動先マスのスコアより経路の長さの方が最終的なスコアへの影響が大きそうということです。かといって実行制限時間内に真の最長経路を求めるのも無理そうですね...。
色々試しましたがマトモなスコアを出せることなくこの日は終了です。これ本番ルール通り4時間だったら何もできずに終わってましたね...。
5日目 12月6日（火）
この時点で私は何故か「DFSをフルで回してなるべく長い経路を作るのは2秒じゃ無理」と思い込んでいました。その思い込みの結果、「毎ターン深さを20以下に絞ったDFS→ドン詰まったら雑に10手戻ってやり直す」という今思うとだいぶ愚かな解法に走ります。この解法でも一部seedでは4万点近く出ますが、100ケース回すと2.6M点に留まります。ダメそう...。
6日目 12月7日（水）
AHC廃人の朝は早い。午前4時に目覚めた藤川は、慣れた手付きでi3wmを操作し、Discordのチームチャットを開いた。その時、藤川に衝撃が走った...！
チームメイトのスコティさんがシンプルなDFSで4.2M点を叩き出していました！！お...俺は何故これじゃ間に合わないと思いこんでいたんだ.....！？
さらにスコティさんは上下左右の優先度設定次第で大きくスコアが変わることも突き止めていて、全24通り試して結果をまとめてくれていました！神！GOD！スコティ神社建てます！！
スコティさんのC++コードをそのまま私の愛用言語であるCrystalに移植して提出してみたところ、スコティさんよりちょっぴり高いスコアを出せてチーム最高得点の座を頂きました。実は私、前回の皆解会001でもチームメイトの解法丸パクリでチーム最高得点を頂くというカッコ悪いことをしてたんですよね。ふじかわひろあきは長いですから、他人の褌で相撲取りerとお呼びください。※このネタ自体がながたかなさんのパクリというハイコンテクストなネタです。
さて、スコアが高くなる移動パターンを見てみるとURLDやLDURなど、「上下どちらか 左右どちらか 左右どちらか 上下どちらか」または「左右どちらか 上下どちらか 上下どちらか 左右どちらか」であることが分かりました。この並びになるのは全8パターンしかありません。またDFSに大して時間がかからないので8パターン全て試して一番良いものを選ぶ方式でも余裕で間に合うことも分かりました。このやり方でスコアが一気に4.6M点までアップ！！！！
個人順位は31人中5位、チーム順位はビリから4位まで上がりました。この時点での最下位は「焼きにゃまし隊」になりました。ふはははは！！ワシらの勝ちじゃ！！やーーいビリ！！！！
......調子に乗っていたのも束の間、なんとこの日の夜までに焼きにゃまし隊は一気にスコアを5.3Mまで上げて3位にのし上がります。ブチギレた私はランキング表管理者のあべみさんにお願いしてチーム名を一時的に「焼きにゃまし隊を焼き払い隊」に変えてもらいました。
7日目 12月8日（木）
朝起きたら個人順位が5位から10位まで落ちていました。は！？！？
そろそろDFSの限界に来ている感じがするので、いよいよメタヒューリスティックなテクニックをブチ込んでいきたいところです。
今回の問題には以下の性質があります。
- 貪欲法（広義）でそこそこのスコアが取れる
- 過去の経路が邪魔になる
これ、AHC014（estieプログラミングコンテスト2022）に似てるんですよね。このコンテストの上位陣は過去の経路の一部を破壊して再構築していました。
似たような解法がAHC002にも使えるんじゃないか？そう思った私は、最終的に焼きなまし法に切り替えることを前提に、まずDFS初期解の一部を破壊して再構築する山登り法を実装してみることにしました。
手順は以下の通り
- 比較的近めの2点をランダムに選ぶ
- 初期解とは別ルートでその2点を繋ぐ
- スコアが上がるなら新ルートを採用（山登りなので）
理屈は単純ですが、いざやってみると無限にバグが生まれますね。22時までかかってようやく完成しましたが、スコアは微増程度（4.6Mから4.7Mに上がった）であまり効果がありません。※後から分かったことですが、この時点では盤面の状態管理にバグがあり、山登りの効果が十分に発揮できていませんでした。
山登りだけだとこんなもんか〜と思いながら、いよいよ焼きなまし法へのチャレンジが始まりました。私はこの時点では一度もマトモに焼きなまし法を使ったことがなく、マジのド素人です。
以下の2つの神記事を参考にしながら焼きなまし法を実装するも、スコアは下がっていくばかり...。この時点では温度が下がっても遷移確率が落ちないバグと格闘していました。
焼きなまし法のコツ Ver. 1.3 - じじいのプログラミング
結局スコアを上げられないまま眠りに就きました。
8日目 12月9日（金）
rinrionさんのアドバイスも参考にしながらようやく遷移頻度がちゃんと下がるようになったものの、やはりうまく焼けません。いったい何がダメなんだ！？温度関数か！？遷移確率関数か！？
この日は何の成果も無く終わりました。気付けば我がチームは最下位で、5Mの壁を越えていない唯一のチームとなりました...。悔しい...。
9日目 12月10日（土）
朝起きたら焼きにゃまし隊のひらさんが「なんだこの集まり、レベル高すぎる」というツイートをしていました。ツイートには順位表のスクショが貼られていましたが、我ら三尺秋水だけ見切れています。これは完全に煽りですね(# ﾟДﾟ) 焼きにゃまし隊、ぜってー全員焼き払ってやる！！！！
焼きにゃまし隊への敵愾心を燃やしながらパソコンに向かいます。これまで焼けない原因は温度関数または遷移確率関数にあると思い込んでいましたが、そもそも山登りによるスコアの上げ幅が小さすぎるということは、盤面の状態管理や更新の方にバグがあるんじゃないかって気がしてきました。
早速盤面の状態を確認してみたところ、実際には通っていないマスも通っていることになってしまっていました。これじゃあうまくいかないのも納得です。
焼きなましの試行回数を稼ぐために盤面のディープコピーという重い操作を避けるようにしていたのですが、まずはバグ取りを優先して、再構築DFS時に毎回盤面をディープコピーするようにしてみました。
これでちゃんとバグが取れることを確認し、seed = 0を放り込んでみたらしっかり焼けている！ローカルテスト100ケース回しても全seedスコア爆上げしている！ちゃんと焼けてる！！いける！！いけるぞ！！いざ提出！！
それまで4.7M台だったスコアが一気に5.8Mまで爆上がりしました！！！！うおおおおお！！！！！！！
焼けた！！ついに焼けたよ！！！！！私でも焼けるんだ！！！！！！！！！
個人順位表を見てみると、私を煽ったひらさんをしっかり抜いていますね。ふははははは！！
しばらく喜びに浸っていましたが、まだチーム最下位なことに変わりはありません。さらに工夫してもっとスコアを上げねば...。
10日目（最終日） 12月11日（日）
ついに最終日。なんとかして最下位を脱出せねば！！
温度関数や遷移確率関数や破壊する範囲を調整してみても大きな変化はありませんでした。一方で焼く時間を制限時間より長くしてみたところ、大幅なスコア向上が見られました。パラメータ調整や破壊・再構築方法の工夫より高速化の方が先決っぽいですね。
焼きなましの試行回数を調べてみたところ、わずか2万回程度しか回っていないことが分かりました。そりゃ弱いわ。
試行回数が少なくなっている原因の心当たりは以下の3つです。
- 毎ターン開始時に盤面を全部更新している
- 経路の一部を破壊する時に、操作列全部に対してループしている
- 経路再構築DFS時に盤面を何度もディープコピーしている
上記2つは比較的簡単に改善でき、試行回数は6万回程度まで上がり、スコアは5.9M台にギリギリ届くようになりました。
しかし盤面ディープコピー問題はうまい解決策が思いつきません。マクロを使った黒魔術など色々迷走しましたがうまくいかず、気付けばコンテスト終了5分前。
もう終わったか...... そう思った時、ようやく有効な改善策が思いつきます。
DFSの1探索が終わる度に探索した分だけループして盤面を元に戻す。一度に破壊・再構築する範囲は小さいので、このループによる計算量の増加はディープコピーのコストよりは遥かに実行速度への悪影響が小さいはずです。
実装してみたところ、試行回数は1ケタ増えて15万回程度まで上がりました！！ローカルテスト100ケース回したところ5.9M台後半〜6Mギリギリくらい！！これはイケる！！！！.............あれ、19時5分じゃん、コンテスト終わってるじゃん(´；ω；｀)(´；ω；｀)(´；ω；｀)(´；ω；｀)(´；ω；｀)(´；ω；｀)
あの時Twitterを眺めていなかったら、あの時おやつをのんびり食べていなければ、あの時ちょっぴりお昼寝をしていなければ....私のベスト提出はタラレバワールドに消えていきました.......。
長渕剛「ろくなもんじゃねえ」を聴きながらモニターに向かって「ろくなもんじゃねえ...」と呟き、10日間にわたる私たちの戦いは終わったのでした.......。
チーム最下位、個人では30人中9位でした。コンテスト後のainemさんローカルシステスでも順位は動きませんでしたが、ついでに涙の5分後提出もテストしてもらったところ、これが間に合っていれば最下位を回避して5位になれたという悔しすぎる事実が発覚しました.............。ううっ！！タラ！！レバ！！アンドろくなもんじゃねえ！！！！！！！
おわりに
順位的には悔しい結果になってしまいましたが、初めて焼きなまし法を使うことができて非常に学びの多いバチャとなりました。主催のainemさん、チームメイト、そして敵チームの皆さんに感謝です。
焼きなまし法やビームサーチといったメタヒューリスティックなテクニックに対して今まで何となく敷居の高さを感じていたのですが、いざ使ってみるとそれ自体は結構単純な理屈であり怖がる必要は無いことが分かりました。
しかし同時に、どうやって焼ける形に持ち込むかを考えることと状態の持ち方や遷移の仕方を工夫して高速化することが非常に難しいことも分かりました。
今回は本来4時間のコンテストを10日かけてチームメイトと相談しながら解くことで本番の上位陣に匹敵するスコアを叩き出すことができましたが、4時間だったら何もできずに終わっていました。私が10日かけて必死で稼いだのと同等またはそれ以上のスコアを僅か4時間で独力で叩き出す強者たちの凄まじさと彼らとの圧倒的な差を痛感しました...。
このバチャを通してようやくヒューリスティックコンテストのスタートラインに立てた気がします。AHCはとても奥が深い最高のネトゲです。私としてはアルゴコンよりかなり面白く感じます。今後も皆解会で修行しながら強くなってやるぞい！！！！永遠に茶下位で停滞してるアルゴコンの方もちゃんと精進しろって？あ、あの、気が向いたらやります、はい....
