AtCoder Heuristic Contest 011 日記編

「AtCoder Heuristic Contest 011(AHC011)」への参加記が長くなったので日記編として切り出した記事になります。

大きく3つの時間軸で振り返りたいと思います。

1. コンテスト開始前
2. コンテスト期間中
3. コンテスト終了後

テキストが多く実際に参加した方以外に共感してもらえる部分があるかは分かりませんが紆余曲折の過程が何かの参考になれば幸いです。

コンテスト期間前（～5/28 AM）

5/25（開始3日前）

いつも使っているPCではなく6コアのマシンを使おうと思い眠っていたPCを起動。IPアドレスが競合しているようで接続が切れる…。設定しなおして再起動。

Pythonはdockerで環境を切り分けて作る。昔、書いた記事を参考に環境構築。Docker側にJupyter notebook, pip, numpy, pandas, matplotlibをインストール。

C++環境は悩んだけどホスト側で構築。g++, VSCode, gitをインストール。

5/26（開始2日前）

Google Testを入れて単一ファイルで動くところまで確認。

5/27（開始1日前）

今回はコードをクラスごとに分割するつもり。提出用に分割したソースをマージする必要があるのでAtCoder LibraryのExpander.pyを参考にスクリプトを作成。

あと、Jupyter notebook側からテストセットを平行実行できるようにしたいけど調査が間に合うかな…。concurrent.futuresで出来そうとわかったところで終了。

5/28AM（当日午前）

concurrent.futuresでサンプル作ったところでコンテストスタート！

コンテスト期間中

5/28 PM（1日目）

問題を見ると15パズルっぽい問題。問題を確認しつつもその夜のABC253で水色になれるかがかかっていた^[1]当時のレーティングが1174だったので気持ちはABC寄り。

ABC253はE問題でハマったけど6完で無事水色へ。よし、AHCを本格的に始めよう。

スコアをみるとトップのmaspyさんが平均764Kまで行ってる。平均的には全域木を求めるのはほぼ出来てて、いかに短い手数でその状態を作れるかの勝負になっている。初日でここまで行くってスゴイな…。

焦っても仕方がないのでルールを整理しつつ自分でテストセットを作る。

• 暫定テスト相当: 50問
• システムテスト相当: 3,000問
• ストレステスト: 10,000問

出来た問題をVisualizerで確認して今日は終了。

5/29 （2日目）

家族でお出かけする日だったので夜帰ってから再開。

• Google Testで複数ファイルをmakeできるようにした
• タイル、盤面を管理するクラスを作って木のサイズを出せるようにした
• Jupyter notebookから平行実行できるようにした。Sanitizerをonにするならdocker側にもg++を入れる必要があった。

と足回りを固めて終了。

あとアイディアを考えてメモに。初期配置から全域木の復元がポイントになりそう。

5/30 （3日目）

仕事が終わるのが遅く夜中に再開。

テストセット3000問を平行実行したが高速化されない…。future.result()で結果を受け取るのがネックで、futureを保存して全部が終わってから結果を受け取ると並行実行数に比例して速くなった。

単純なDFSをお試し実装。200K回探索すると平均スコア146Kくらい。何もしない（54K）よりはずっといいが、最大でも286Kで全域木を見つけることはできていない。
一度、submitして平均スコア150Kで252位。

5/31 （4日目）

早めに仕事が終わったのでもりもり実装。まず全域木を復元するための焼きなまし法。

• 初期配置: 空きマスを右下へ移動
• 近傍: 種類の違う2つのタイルをswap
• コスト: 閉路有無と隣接関係の違反

を考えて回した。最初、全然ダメで焼きなまし法だとダメか…と思ったが、余りにもダメ（まったく連結されていない）なのでよくよくコードを見たら悪化した場合も元に戻らない猪突猛進ロジックになっていた。

直したら期待した結果になっていて50個中1個全域木ができている！おおースゴイやんと一人勝手に感動。

タイルの枝が伸びている方向ごとに置ける場所が限られるので置ける場所を限定してswapすると一気に改善して50問中29問で全域木が求まっている！素晴らしい。

初期状態から目標状態にするロジックを実装。乱暴かなと思いつつBeam searchで。焼きなまし法50K回、Beam search 50K回で全域木を出せるサンプルが出た！方針として大きくは間違っていなさそう。ただ、時間が平均で4,901ms, 最大で7,735msなので高速化しないといけない。

seed=0が解けてちょっと感動。

ただ、最初からBeam searchは無理筋っぽい。左上から順にルールベースで埋めていけば手数的に非効率だけど確実に全域木を作れるのでは？と考え始める。

懸念は操作回数の上限に収まるか？で、斜めに進むと3手/マス、上or左に進むと5手/マスかかるので平均4手/マスとして移動距離が平均N/2マスくらいとすると[math]4 \times N/2 \times N^2= 2 \times N^3[/math]でピッタリ！まずはルールベースで確実に全域木を出せるようにしよう。

寝る前にストレステストを投げて終了。

6/1 （5日目）

ルールベースで埋めていくロジックを実装。最初、目標地点は開始地点より上 or 左にあることを仮定していたけどそれ以外のケースも対応させないとうまく配置できないことに気づいて書き直し。結局、空きマスの「通過不可フラグ」を持って移動済みのタイルを触らないようにした。

あとハマったのが上の図のパターンで3のタイルを一度退避させないと配置が不可になる。どの場所に退避させればよいか悩みつつ寝ようと思ったけど布団の中で黄色の場所におけば大丈夫だと気付いて思わず実装。これ…明日絶対辛いな…と思いつつ実装。

目が冴えてしまったので開始位置から目的のタイルを拾って目標位置に持っていくのをダイクストラ法で書いた。ただ、「今までの移動距離＋残りの推定移動距離」とするところを「残りの推定移動距離」だけにしてて激重ロジックにしてしまった。何とかデバッグしてさすがに寝ることに。

ボトルネックはもう別のところに移ったと思うけど明日プロファイルを取ろう。

6/2 （6日目）

必要なロジックはほぼ揃い、最後[math]2 \times N[/math]を全探索するBFSを書く。[math]N=3, 4, 5[/math]で試すと[math]N=5[/math]はすべて目標状態に到達。Parityはそこまで神経質にならなくてよさそう。ただ、[math]N=5[/math]は計算時間的に間に合わず[math]N=4[/math]を設定。これだと90%くらいで求まる。

焼きなまし法の反復回数を調整して3000msに収まるようにしてsubmit。平均スコア548Kまで行って500K越えの世界に到達！

パズルパートはいったん終了で焼きなましパートに戻ろう。

焼きなましパートを改めてみると

• コスト: 連結性の違反状況を評価
• スコア: 最大木のサイズ

で今まで「コスト最小」の結果を返していたけど欲しいのは大きな木なのでコスト基準で探索しつつ「スコア最大」の結果を返すよう変更。ほぼ全域木に近い結果を出せるようになった。

あと焼きなまし法で試行回数を増やすとなぜかスコアが下がることがあって不思議に思っていたら温度を決める進行状況(progress)という変数が

double progress = 1.0 * i / loop_count;

となっててloop_countを増やしても時間分解能？が上がるだけでloop_countが小さいケースを含んでいる訳ではなく必ずしもスコアは上がらない…というわけか。うーん、理解はできたが気持ち悪いな。

あと初期配置で設置不可な位置にあるタイルを設置可能な場所に移しておくと性能が上がった（反復回数を100Kから75Kにしてほぼ同じ性能）

ただ、設置可能なswapがない…という驚きの配置があってそれが下の図。

青枠のマスと残りのどのマスをswapしても矛盾してしまう…。ただ、あまりこだわるポイントでもないので適当な回数試してダメなら諦めて矛盾した配置を採用することに。

プロファイルを取ったらやはりボトルネックは焼きなまし法の閉路判定になっている。
UnionFindで判定していたので連結成分の部分更新（必要な分だけバラしてunionしなおす）をかなり苦労して実装したが速度が微妙に悪化するという超残念な結果に…。

コードは戻して柔軟に処理が書けるよう連結成分をDFSで出すようにして今日は終了。

6/3 （7日目）

この日は有給を取得して一日競プロ三昧…のハズが眠い。

最近、なぜか性能が落ちていててぼーっとした頭でその原因究明。これが迷走して

• gitで切り戻して性能が悪化したポイントを探す
• どうも「初期配置で設置可能な場所になるようにswapするが、不可能な図がありえるので一定回数で切り上げる」を入れたところで性能が劣化したっぽい
• 不思議なことに他にも不要な乱数呼び出しを1回削ると性能が劣化する！？？

となって何が悪いのかよく分からない状態に。

N=50くらいのテストだと乱数によるブレなのか性能による差なのかが分からなくなってサンプルをN=3000まで増やした結果、

性能劣化は起きていない

が結論。疲れた…が、乱数を使うアルゴリズの宿命か。

あとは連結成分が知りたいのではなく、「最大の木」が更新できそうかだけを判定すればよい…という観点でいくつか高速化できそうなポイントを考えたけど、如何せん眠くて実装しても怪しいのでちゃんと寝て頭をリフレッシュしてからやろう。

6/4 （8日目）

連結成分を求めるDFSがやはりボトルネックで再訪チェックをsetでしていたのをテーブル化したら15%くらい高速化した。

あと温度の進行度の分母は試行回数ではなく固定値を使うように変更。ハイパーパラメタが1つ増えるが試行回数を増やすについれて単調に性能が改善するようになった。

焼きなまし法の温度パラメタのチューニング。4時間くらいかかる見込みだったのでPCに頑張ってもらう横でお昼寝。

チューニング結果を見ると最終温度をあまり下げないパラメタが良くなっていた。全域木になる解がそれなりにあってランダムswapを継続するのがよいってことなのかも。

あとパズルパートの2 x 4領域の全探索時に目標状態との差分を最小化して0になればよいが、差分が残るときに中くらいの木に分割されることがあり非効率だけど木のサイズを求めて最大のものを出すように変更。

いったんsubmit。平均573Kまで伸びたが順位は103位。やはりみんな伸びている。

ここで残課題を整理。

• パズルパートの手数の短縮
  • 左⇒右と詰めているが右⇒左と詰めるのも用意する
  • タイルを動かすルートが2つあるときに目標に近づく方を回る
  • 焼きなましパートでそもそも初期配置から近いものを探す
• 焼きなましパートで全域木を見つける割合を増やす
  • 連結できない成分は右下に寄せる（最後の全探索で全域木が見つかるかも）
  • 焼きなまし法のパラメタ調整
  • 速度を上げて2回回せるようにするか、探索回数を減らして複数回回すか。

焼きなましで全域木を求める割合を増やすのは難しそうなのでパズルパートへ。

手数を短くするために右詰、左詰の推定手数をもとに右、左を選択しようとしたが推定のブレが大きくてうまく行かず。

冷静に考えると右、左の2通りしかなくDPで最短手数が求まることに気づいて実装。思った以上にサクッと実装できてこの辺りは成長を実感。スコアも7%くらい伸びた。

寝る前に焼きなまし法の評価関数に初期配置からの距離を入れてテスト。平均で3Kくらいスコア改善。

6/5（最終日）

AHC011もあっという間で今日がラスト。昨日寝る前に考えた列単位で埋めると端のエッジの有無と残りのタイルの枚数で状態を表現できBitDPで扱えないかと朝から考察。

残念ながら全部の状態を持つのは難しそう^[2]各列で最大1024 x 1024のチェックが走るのでで左端と右端だけ作って左からランダムに伸ばしていって右に着いた時に整合性の取れる図を作れるかでチェックしようとした。15時くらいまでやったが整合性を満たした図を作るには計算量的に厳しい…という結論になって断念。

冷静に計算量を評価すれば無理筋だと気づけたはずが変にこだわってしまった…。

気を取り直してボトルネックになっていた連結成分の算出を省く検討へ。

• 近傍生成⇒閉路判定⇒コスト算出⇒更新判定

を

• 近傍生成⇒コスト算出⇒更新判定⇒閉路判定

とするだけなのに何度も謎の性能劣化を引きおこして都度Gitで復元。Gitで管理しておいてよかった。4度目の正直で解答能力そのままで4倍近く速くなる実装にたどり着いた！

これで一気に開けてきて焼きなまし＆パズルパートを複数回回せるようになりsubmit結果も平均573Kから657Kに100K以上ジャンプアップ。

多様性を出すため焼きなましの初期化を「乱択DFS」と「初期配置そのまま」を交互にやるようにしたら平均5Kほどアップ。

焼きなましの反復回数を増やしても計算時間はあまり変わらなくなったので75Kから500Kに増やしさらに平均7Kアップ。手元の50問はすべて全域木を求められた。

最後にパズルパートを動かす条件をバグらせて一度、全域木解が求まると二度と更新されなくなっていたのを修正。平均706Kまで伸ばして終了！


コンテスト期間後

Twitterで参加者の解法を眺める。印象に残ったのは全域木の復元は

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

は目からウロコ。途中苦しんだUnionFind使った連結成分の管理も「Rollback付きUnion Find」というのがあることを知りました。

パズルパートもある程度のサイズまで埋まったらBeam searchなりIDA*なりで探索するのが良かったみたい。なるほどー。この時間が一番楽しいかもしれません。

かえでさん^[3]お仕事、家事、育児をしつつ競プロにのめりこむ？様子をつづったtweet, blogをいつも共感しながら見ています。がTwitterでスペース（トークルーム）を開いていてて参加したかったけど土日にやる予定だった用事を片付けるのに精一杯で参加できず。次回は日常生活含めたタイムマネジメントをちゃんとして参加できるようにするのが目標ですね。

最後に作問のwataさん、運営のAtCoderの皆さん、そしてTwitterで共有してもらった皆さんありがとうございました！

脚注[+]

脚注

↑1	当時のレーティングが1174だった
↑2	各列で最大1024 x 1024のチェックが走るので
↑3	お仕事、家事、育児をしつつ競プロにのめりこむ？様子をつづったtweet, blogをいつも共感しながら見ています。