AtCoder Heuristic Contest 001 参加記

はじめに

反省点の一つでもありますが、コンテスト中に記録をつけることを怠ったため、以下の内容は僕の記憶に基づいており、不正確な記述を含む可能性があります。

参加にあたって

AHC は個人的にかなり楽しみに待っていました。その記念すべき第一回ということで、今回僕はガチ参加しました。多少中だるみもありましたが、期間中のかなり多くの時間をコンテストに使ったと思います。

ところで弊社jobsアルバイトerのうち、マラソン強い勢がAHC001期間中のためマラソン休暇を取っているのですが、私にも欲しい。

— ツカモ (@tsukammo) 2021年3月8日

恐縮すぎる。
言語は Rust を使用しました。Rated コンテストで使うのは初めてです。

結果

スコアは 991,112,901,526 で順位は 19 位でした。

解法

「領域全部を広告で埋めた状態で焼きなまし」です。

初動で「広告を 1 マスずらしたり 1 マス拡大縮小したりする焼きなまし」を実装しましたが、あまりスコアが出ず、座標がほとんど連続量であるために解空間が大きすぎるのが良くないと考えました。そこで、状態の重要なパラメータを各点の座標というより広告同士の隣接関係にすることで、状態空間を実質的に狭めたいという考えがありました。なお、広告が大きすぎる分には焼きなましの後に削ればいいので全く問題はないです。座標がほとんど連続量であることがここではメリットとして効いています。
焼きなましの近傍としては
① 連なっている線分を動かす
② 2 頂点を共有する 2 つの広告について、境界となる線分の縦横を入れ替える
③ L 字型をなすように隣接している 2 つの広告について、境界となる線分をスイッチする
の 3 つを用意しました。これらがあれば状態空間を結構広く探索することができると思います。(完全に連結かどうかはちょっとよくわからないです……。)

ひとつひとつの広告を長方形として持つような実装になっています。隣接関係などは遷移の度に更新するより評価の都度に調べたほうが高速でした。

反省

僕の方針で良くなかったのは、最終的な解を限定してしまっている点と、多峰性が強いのに kick 近傍を取り入れるのが難しい点だと思います。「領域を完全に広告で埋めるのではなく、四畳半の真ん中のような隙間を空けることを考慮する」ことでこれらを同時に解決することが可能だと思っているので、今度実装してみるかもしれません。(隙間を空ける考え自体はコンテスト中からあったのですが、kick 近傍については気づいていませんでした。高速に動作するような実装がかなり難しいので今の解法を詰めるのが優先だと判断してしまいましたが、気づいていれば踏み切れていたかもしれません。)
また今回、マラソン系コンテストに挑むにあたっての事前準備がかなり不足していました。ビジュアライザを作るための何らかのフレームワークに習熟し、並列実行ができる環境も整えなくてはなりません。並列実行の環境ができていなかったために手元で試すケース数が不十分であり、(運良くシステスでは踏まなかったようですが) バグを埋めたことに気づきませんでした。Rust の知識が付け焼き刃すぎて困る場面も多かったです。Rust 自体はいい言語かつマラソンにも適していると思うので次回以降も使っていきたいです。

感想

ガチ参加したので多くの方々に勝つことができましたが、ガチ参加しても 18 名の方々には勝てなかったのが悔しいです。
自分はわりとアルゴよりもマラソンの方に適性があると思っているので、AHC は今後も頑張っていきたいです。