AHC013参加記録

AHC013参加記

お疲れ様です。AHC013(RECRUITE 日本橋ハーフマラソン2022夏)に参加して平均7435点くらいの8位でした。 コンテスト中にやったことを書いていきたいと思います。

atcoder.jp

最初に問題を見た感想

  • AHC011とMM139っぽい見た目をしている... ゲーム性は全然違いましたが、一部参考にできるところはありそう
  • NとKの値によってだいぶゲーム性が違いそう
    • この点でAHCよりもTopCoder MMっぽい感じの印象を受けました。
      盤面の大きさによってかなりゲーム性が変わりそう
  • 点数のつき方からして一つの色のコンピュータを全部つなぐことが大事そう
  • 上位陣は3つくらい繋げてくるんだろうなあ

1日目 (8月9日)

問題を見て3つの方針を考えました。

  • 方針1. ビームサーチ
    • 適当な評価関数を作って、適当な遷移をする? 手数ごとに状態を管理して、大きなコンピュータのクラスタにボーナスをつけるとか?
    • ただ、一つの局面でとりうる手段がいくつもありそうで、しかもそれは順番的に独立なことが多そう。ある局面でクラスタ同士をくっつけるのに別々の箇所でA, B, Cの手段が3つあるとき、3ターン後にはABC全部やった状態だけが残ることになりそう。
    • 多様性を確保できるのか? 単純にABC全部やった方が良くない? ということでビームサーチはお預けに
      • と当時は思っていたんだけれど、どうなんだろ? まあ状態の管理がコストが高そうだったから、貪欲+乱択の方針はそんなに悪くなかったと思う
  • 方針2. ルールベース
    • ノートに"端っこにタイルをめっちゃ動かすとか、互い違いに色をつなげるとか?" こういう記述が残っていました。
    • inaniwaさんがあげてくれた↓みたいなのをやりたかったんだと思います
    • 密な時に上手くできる自信がなかったので一旦お蔵入り
  • 方針3. 焼きなまし
    • AHC011の時の記憶が残っていて、最初に都合のいい木を焼きなましで作って、そこに向けてコンピュータを動かしていくことを考えました
    • 木の頂点や根っこには必ずコンピュータを置かないといけないのでその点はめんどくさそうだけど、上手くやったら筋がよいのではと考えていました
    • 盤面に色が多過ぎたり、盤面が密だったらコンピュータを動かすのが大変そうだったので、K=2でN=30くらいの時でまずやってみる

この中からまずは焼きなましを採用してやってみようということになりました。

2日目(8月10日)

この日はお盆前の最終の仕事の日でした。 焼きなましをしていく上でまずビジュアライザを自作しました。 コンピュータの配置とは関係なくケーブルを表示したかったっためです。ちなみにpythonのplotlyというライブラリを使っています。

自作したビジュアライザ

ビジュアライザを作ったので、次に完成図の木を焼きなますロジックを書き始めました。 近傍は結構適当だったんですが、こんな感じにやっていたみたいです(もはや記憶が...)。

近傍のメモ

3日目(8月11日)

焼きなましを挫折

焼きなましのロジックを完成させたのですが、ちょっとイマイチな感じでした。近傍と評価関数が適当だったので、局所的な構造を捉えることができず微妙でした。

焼きなましした図。下の真ん中付近の青の囲いの中に赤いのが混ざっている時とかが対応できていない。

新しい方針

評価関数と近傍を作り直してやってもよかったのですが、むしろ局所的な構造から出発してそれを繋げていくことのほうが有望に思えました。 ある色に注目して、近くにあるコンピュータ同士を繋いで、それを段々と大きくしていくやり方ですね。下の図を書いたら結構いけそうな感じだったので、これでやっていくことにしました。

連結できる部分を繋いで、それを徐々に大きくしていく

上の絵を見ると連結している部分を繋いでいくためには、以下のようなことをやれば良さそうです。

  • ①連結成分間の邪魔になっている別の色のコンピュータを取り除く
    • これはむしろ別のところから空白を持ってきて埋めるというようなイメージです
    • 間に複数個の別の色のコンピュータが入っていても対応できるようにしました(たくさんある場合は後回しにする)
  • ②連結していないコンピュータを動かして連結させる
  • ③つながっているコンピュータのうち自由度がある箇所(端っこや角になっていないコンピュータ)を動かして繋げられるかやってみる

連結成分を大きくしていく戦略

ここまでやると最後に下のような状況が残りがちでした。こういうときには、くっついていないコンピュータの一番近くにある空白セルを動かすようなスライドパズルの問題にして、DFSの要領でくっつくまで全探索させました。

方針は決めたので、これを泣きながら実装しました(マジでつらかった...)。

4日目(8月12日)

ひたすら実装

上の方針を全て実装し終わったのがこの日の16時くらいです(丸一日実装と考察にかけました... マジでつらかった)。 seed1がつながったので、とりあえず提出しました。206k点で当時37位でした。いい感じ。

seed=1が最初に繋がった時の図

上手くいかないところの改善案を出す

手元で上手くいかないところを調べたら、密な盤面でうまくいっていないことが多かったです。

上手くいかない時
上の図などをみると、木の辺を作る時に無駄に空白セルを使ってしまっているように見えます。 密な盤面では空白のセルが重要で、クラスタ同士をくっつける時に間に空白のセルを移動させて繋げることが多いので、極力無駄遣いは避けたいです。 そこで、以下のように木から空白セルを解放するような操作を追加しました。
空白セルの解放

これをやると密な図面でも完成する確率がかなり高まり、提出したら248kで14位まで上がりました。(1本目が完成したら残った手数で残りの箇所を適当に繋いだ)

5日目(8月13日)

作る色や操作の順序に乱択性を持たせて時間いっぱい探索やってみたら全ての図形で木が完成するようになりました。微改良も含めて260k点になりました。

次は2本目の木をまともに作れるようにしなければいけません。 例えば次のような図を見ていたのですが、連結な成分が1本目の木によって大きく分断されていて、木をあまり大きくできそうにありません。

1本目の木が出来上がった状況

一体どうやって大きな連結成分を作ればいいのか困っていました。有力そうだったのが1本目の木の辺をつなぎかえる近傍で焼きなまし/山登りをすることですが、

  • 辺をつなぎかえるのにコンピュータを動かさないといけないとなるとコストがかかる
  • 繋ぎかえる場所の選択が難しそう

ということであまりやりたくありませんでした(正直実装にかなり疲れていました)。

連結成分を大きくするのは大事そうではあるんですが、何はともあれ連結成分の中に2本目の木をできるだけ大きく作ること自体は無駄にならなそうです。 ということで連結成分を大きくするのは一旦後回しにしました(これは良い判断でした)。

1本目の木を壊さないように2本目の木を作る実装を始めました。使ったロジックは1本目の時と大体似たような感じです。

6日目(8月14日)

2本目の木を最大の連結領域で完成させた

こんな感じでした。これで320k点です。この辺りでTシャツ圏内が確定した感じですね。

2本目の木を最大の連結領域で作る

ここまでは割と常識的な手段をまっとうに積み重ねてきた感じだと思います。理詰めでここまでできたのは結構自信になりました。

連結領域を大きくするアイデア

後回しにしていた連結領域を大きくする方法ですが、簡単にできる方法を思いつきました。 1本目の木を作るときに、周り2マスを空けて構築して、周り2マスで2本目の木を連結させるような方法です。

とりあえず適当なインプットを用意して、1本目の木を周り2マス空けて構築してみました。

連結領域を大きくするために盤面に余裕がある時には周りに空白を開ける
この図を見てこの方針がかなり有望そうであることを確信しました。全部の領域が連結していて、周りからアクセスしやすそうですね。

基本的な方針としては、

  • KとNが大きな図では外周2層を開ける(ここのところは後で調整しました)
  • 2本目の木の色は外周から2層目に置く。外周で1周させるため、2層目の4隅のうち3つには必ずコンピュータを移動させる。
  • 外側から2層目にある使わない色のコンピュータは移動させる。できるだけ一番外の層に捨てる(内側にやると邪魔になるため) 。

この方針を実装したら359kまでスコアが上がりました。2本目の木が初めて完成しました。

初めて2本目の木が完成したとき

7日目(8月15日)

更なる改善ができないか検討して諦めた

完成後の木と初期盤面を見比べて、移動をサボれるところがないかを検討しました。 移動の量が多いノードを別の箇所にくっつけることで手数を省略できないかやろうと思ったんですが、難しそうだったので断念。 焼きなましの初期配置としては結構良さそうで、これをもとに焼きなましができればよかったと今は思います。

初期配置と木の完成後の比較の図。緑色と青色が完成後の木のノードである。緑色のノードは初期盤面からコンピュータが置いてあった場所、青色のノードは初期盤面にはコンピュータがなかった場所。赤色の点は初期盤面にコンピュータがあった位置で、最小費用流で最も近い青色のノードとの間に線を引いています。

色々微修正

細かなところの手順とかパラメータを改善して、最終的に378kくらいまでスコアが上がりました。 手順の順番のランダム性などを強化したのが効いたように思います。

8日目(8月16日)

余った手数でコンピュータをつなぐ

2つ目の木が完成してしまったり、中途半端に手数が余ったりしてしまうことがありました。 残りの手数を使って盤面を動かさずに繋げるコンピュータをつなぐようにしました。

バグ修正・微修正

手元(AWS)で大量のテストケースを実行させて、思わぬところのバグがないかを調べていました。 2000ケース実行してみてスコアや実行時間をプロットしてみたところ、以下のような感じになっていました。

おおむね2.9秒くらいで打ち切られているのですが、ごく稀に実行時間がはねて3秒近くになってしまっていることがあります。 これは一部のDFSで再帰処理をさせているところが条件によってとても時間がかかってしまい、実行が終わらなくなっていることが問題のようでした。

DFSの打ち切り条件を改善したら実行時間がまともな感じになりました。これで最終提出にしました(382kくらい)。

その他

  • 最終的な順位は8位で、自分の実力からすると信じられないくらいの好成績でした。
    • 運よく良い方針が降ってきたのと、お盆休みが重なってAHCに集中できたのがよかったのだと思います。
  • 実装がつらかった...
  • 次回は日記をちゃんと書こうかな。Githubのissueから情報を抜き出してくるのが大変でした。
  • 方針がiwashiさんのものと結構よく似ているような気がしています。
  • 構築中の様子はこんな感じでした:

次回のマラソンも楽しみです。Asprovaコンテストかな? 次回も対戦よろしくお願いします。