AtCoder Heuristic Contest 011 参加記

競プロサイトAtCoderで開催された「AtCoder Heuristic Contest 011(AHC011)」に参加し2,105,121,037点の87位になりました。

1週間強の長丁場の足取りを参加記として残したいと思います。流れは

1. コンテスト／問題概要
2. はじめに（自己紹介）
3. 提出解法
4. ヒューリスティックコンテストでの工夫点
5. 結果
6. 日記編
7. 振り返り
8. 感想

で、日記編は長くなったので別記事にしたいと思います。

方針、解法はオーソドックスだと思うのでこんな解法でもこれくらいの点数は取れるんだという参考にしてもらえれば幸いです。

コンテスト／問題概要

AtCoderでは大きく2種類のコンテスト

• アルゴリズムコンテスト（最適解や厳密解を求められる問題が出題）
• ヒューリスティックコンテスト（最適解を出すのが難しい問題が出題）

が開催されており今回はヒューリスティックコンテストになります。

アルゴリズムコンテストと比較すると

• そこそこの時間でそこそこ良い解が期待できるアルゴリズム（焼きなまし法など）の知識も問われる^[1]もちろん部分問題が最適解を出せる問題になることもありアルゴリズムコンテストの知識も役に立ちます。
• 取り組む時間が長く設定される（今回だと1週間強）

のが特徴です。

問題概要

要はバラバラになったタイルが与えられるのでうまく少ない操作で「全域木」を作ってください…という問題になります。

はじめに

簡単に自己紹介すると

• 大学は連続最適化が専門。離散最適化も一通り知っているのでバックグラウンドはちょっと有利？
• 卒業後はデータサイエンス領域のコンサルがお仕事。若手の時はプログラムを書くこともありましたが管理職になってからはほぼゼロ
• 職場で競プロが話題^[2]当時、新人配属の基準にKaggleだけではなく競プロも含めるか？や部署の表彰制度に競プロを含めるか？という議論が職場でありました。になったのをきっかけ^[3]余談ですが職場の表彰制度にAtCoderを推薦したら入りました。管理職など会社の意思決定を担っている人のファン、理解を得ることも大切ですねに2022年1月からAtCoderのアルゴリズムコンテストに出始めた
• アルゴリズムコンテストは5月に水色になった

で「ヒューリスティックコンテストの方が最適化の経験が活かせるかな～」「長期コンテストの方が瞬発力勝負にならなくていい^[4]この時は持久力勝負になるとは思っていなかった…かな～」くらいの気持ちで参加しました。

提出解法

「バラバラのタイルから全域木（目標状態）を作る」のと「少ない操作で目標状態にする」のを同時に行うのは難しいと思ったので大きく2つのパートに分けました。

1. バラバラのタイルから全域木（目標状態）を作る
2. 与えられた状態（初期状態）をできるだけ少ない操作で求めた目標状態にする

Step.1 目標状態の探索

焼きなまし法で探索を行い250ms程度の探索で以下の評価関数／近傍／初期化を用いて90%程度の割合で全域木が求められました。1回で全域木が求められなかった場合は複数回繰り返すことで対処しました。

評価関数

評価関数には以下の2つの観点を盛り込みました。

1. 各タイルから見た隣接するタイルとの接続関係
2. 初期状態からの距離

具体的には各タイル（下図の赤枠タイル）と隣接するタイルを見た時に以下の違反

• タイルから枝が伸びているが隣接タイルから伸びていない
• タイルから枝が伸びていないが隣接タイルから伸びている

がある場合にコストを与えました（タイルが連結するとコストが下がる）。

また、初期配置と近い配置ほど操作回数が減ることを期待し各タイルで初期配置で最も近い同種のタイルとのマンハッタン距離も加えました。ただ、連結性を重視し隣接関係のコストは違反1つにつきコストを2000加算^[5]初期状態からの距離は高々18×100=1800なので隣接関係を優先してみることに対応します。するようにしました。

近傍定義

近傍は「ランダムに異なるタイルをSwap」して生成しました。ただし、タイルの枝の伸び方によって置ける場所が限定される（ex. 十字のマスは盤の辺に置くと連結するタイルがないので矛盾）ので置ける場所に限ってswapするようにしました。

また、閉路判定を行い閉路が生じるswapは行わないようにしました。

初期化ロジック

基本は以下の4つのステップで初期化しました。

1. 空きマスを右下に持ってくる
2. 左上の角から乱択DFSでタイルを隣接関係の矛盾のないように埋める。残りのマスはランダムに置く
3. 閉路があればswapして壊す
4. 置けない場所にあるタイルを置ける場所にswap

としました。複数回回す時は多様性を出すために2.は「乱択DFS」と「初期配置そのまま」を交互に行うようにしました。

最後に温度パラメタは開始時の温度が1000, 終了時の温度が500で違反が1-2個になった後もswapを継続する設定が良かったです。全域木になるケースがたくさんありswapを積極的に繰り返した方が全域木が求まりやすかったのかもしれません。

目標状態への手順探索

「★15パズル攻略法★」を参考にルールベースで解きました。ポイントは

どの位置のタイルも目標位置の下 or 右のみを通って置くことができる

です。

上の図で言うと置きたいタイル（青枠）を置きたい場所（赤枠）に赤枠の下 or 右の領域（薄黄色の領域）だけを通って移動させることができます（青枠のタイルを回り込むようにして上、左へと移動させる）。

このことから左上から順にすでに置いたタイルを動かすことなく一行ずつ揃えることができます。ただ、最後の右端の部分は少し工夫が必要で「1 2 3 4」と並べたいときに

と置いて右隅の空きマスを「左⇒下」とすることで求める配置にできます。

ただし注意が一つあって4を配置した時に下図のように3が空きマスの直下にいると配置が失敗します。

4を置く前に3を退避（上図の黄色の位置）させ4を置いてから3を置けば配置失敗を避けることができます。

目標状態にするために持ってくるタイルは貪欲法で移動距離^[6]斜め方向は3手で1マス、縦／横方向は5手で1マス移動可能が最も小さいものにしました。これを1からN-2行目まで行い、残り2行になったら同様に左から1列ずつ並べ残り2 x 4の状態になったらBFSで全探索しました。

手数を短くする工夫はあまりできなかったのですが各行で「左から埋める」「右から埋める」の両方を解いて1～N-2行全体として手数が少なくなるようにDPで左右どちらから埋めるかを決めました（これで7%くらいスコアが上がった）。

ランダムに目標状態を作っているため1/2の割合でParityがずれて解けないことがあります。ただ、同種のタイルが2 x 4の範囲に複数あれば解け実際、手元のサンプルでは90%の割合で解けたので時間のある限り別の目標状態を作って解くことで対処しました。

ヒューリスティックコンテストでの工夫点

短時間勝負のアルゴリズムコンテストと違いヒューリスティックコンテストは1週間強かけて考察＆数千行のコーディング＆メンテしないといけないので以下を行いました。

• 適切にクラス化を行う
• クラスごとにソースコードを分割する（コンパイル時間短縮＆メンテが楽に）
• 提出用ソースコードのマージを自動化(AtCoderライブラリのExpander.pyに相当)
• 機能ごとにユニットテストを行う（品質向上＆リファクタリングがしやすくなる）
• Sanitizerを使って実装バグを検知（配列アクセスバグなどを検知してくれ便利）
• Gitでコードを管理して戻れるようにする（何度も助けられた…）
• Jupyter notebook, Excelで結果を可視化（モチベーションUp）
• 手元でサンプルケース（50問, 3000問, 10000問）を用意
• サンプル実行は並列化し高速化(6コア12スレッドのマシンで9並列実行)

ヒューリスティックコンテストだと保守性など実務的な工夫も求められると思います。

結果

50問での暫定テストで35.3M点（平均706K点）で86位、3000問でのシステムテストで2.1B点（平均702K）で最終87位でした！

最終順位は1つ落としてしまいましたが、全域木が求まらないケースが0.5%くらいあって暫定テストでは運よく出なかったけどシステムテストでは期待値分くらいはそのケースが出て実力通りの結果になったのだと思います。

99.5%のケースで全域木を完成させることができ操作数の短縮もかけた時間が短かった（初期状態から目標状態を作るロジックの実装で手一杯だった）割には良い結果で満足しています。

最後に手元のテストケースでスコアが最小だったものと最大だったものを紹介して解法の解説を終えたいと思います。

スコア最小のケース

• Input: 6 432 358891 8e1666 315bbd eb6c8b eb0514 8e242e
• [math]S=33, K=296, {\rm Score}=471,429[/math]

まず目標状態を探す段階で全域木を見つけられず目標状態を作るパートでもParityが合わず作ることに失敗しています。

今思うと目標状態を探す時に違反するマスの場所を優先して右下2 x 4領域になるようにしておけばBFSで全探索するときにうまく回避できたかも…と思います。

スコア最大のケース

• Input: 8 1024 f2465d93 ac5ce693 0819f556 539c4c75 8aaca598 66583c63 52965159 39aa7536
• [math]S=63, K=466, {\rm Score}=772,461[/math]

アニメーション見ると我ながら？頑張って解いています。トップ層はこれの半分くらいの操作数で全域木を完成しているのでホントにスゴイ！と思います。

日記編

今まで説明した提出解法はすんなりたどり着いたわけではなく1週間、紆余曲折しながら進んだ結果です。ここからは当時のメモをみながら時系列で振り返りたいと思います。
全体が長くなったの日記部分は別記事にしました。そちらを参照ください。

振り返り

AtCoderの良いところは終了後にTwitterで活発にアプローチや解法の情報が交換されることですね。今回の問題でも色々なアプローチができたようです。

目標状態の探索

全域木の作り方も色々なやり方ができたみたいです。私は「ばらばらのタイルを連結させよう」「いい解法思いつかないので焼きなまし法で」で思考が止まりましたが

• がんぽんさんによる「DFSで木を作る方法」（DFSで作れるとは思わなかった！）
• Terryさんによる「全域木を先に作ってタイルの種類を合わせる方法」（先に木を作る発想はなかった！）

は見ていて目からウロコが落ちました。

他にもParityの関係で1割くらい解けない配置になるので「BFSを行う2 x 4領域に同種のタイルが2枚入るように決め打つ」のも良かったのではと終わってから思いました。

目標状態への手順探索

上位層はここをどれだけうまくできたかで差がついたようです。確かにそうした方が良いなと思った工夫は

• 目標状態と初期状態の対応付けは最小重みマッチングで行う（気づいていたけど最小マッチングを書いたことがなく貪欲法に逃げた…）
• 序盤はルールベース、ある程度埋まったらビームサーチやIDA*で操作数の少ない手順を探索
  • ルールベースも複数枚まとめて移動させると手数短縮になる
  • 探索も半分全列挙的に開始／終了盤面の双方向から探索する
• 探索しながら改めて移動させやすい全域木を求め直す

です。

今回は焼きなまし法の高速化に手間取ってパズルを解くパートに時間をかけられなった^[7]それでも左右どちらか埋めるのかを決めるDPを一発で書けたのはアルゴで鍛えられたおかげだと思います。のでそれぞれにバランスよく時間をかけられるようになりたいですね。

生活面

アルゴリズムコンテストのように瞬発力は求められない反面、1週間近くのめりこんで^[8]それだけ面白い問題ということですが。他のことがおろそかになりがちだったのでバランスを考えないといけないですね。

この1週間は

• 寝るときもついつい考えてしまって浮かんだアイディアをメモったり、実装したくなり夜更かし
• 次の日は睡眠不足でヘロヘロで早々に爆睡
• その次の日は復活してまた考察＆実装にのめり込んで寝不足に…

を繰り返していました。性格に起因している面もあって難しいですがより短時間で良い解法に行きつけるようになるのが解決策^[9]Twitterでみんな没頭しているのをみて結局、締め切りまで改善を追い求めそうですが…でしょうか。

あと月曜に週明けとは思えない疲労感（と達成感）が残ったので持久力も必要ですね。

感想

最初見た時はアルゴリズム寄りの問題であまりヒューリスティックスっぽさはないかな？と思いましたが最後までアイディアは尽きず試行錯誤をして、幸運なことに最後日にスコアを平均573Kから706Kまで伸ばすことができました。

コンテスト期間の1週間は余暇の時間＋睡眠時間の大部分を注ぎこむくらいのめり込めましたし、終わった後のTwitterでの解法紹介も目からウロコの解説が多くて勉強になりました。作問のwataさん、運営のAtCoderの皆さん、そしてTwitterで共有してもらった皆さんありがとうございました！

参考

• 15パズルの解法: ★15パズル攻略法★
• Terryさんの解説記事: 「AtCoder Heuristic Contest 011 (AHC011) 解説」
• かえでさんの参加記: 「実録！AtCoder Heuristic Contest 011参加記」