ごりちゃんがゆく

競プロをするゴリラの精進記録

AHC011 参加記

AHC コンテスト参加記

書くか～～！ (書きます)
AHC011に参加しました！！

9日間のコンテストをどう戦ったか、時系列の日記形式で書いていきます！
これを書いてる今はコンテスト終了5日後ですが、メモやツイートを頼りに思考の流れを再現したいと思います。※最後まで書き終えたのはこれのさらに2か月後です 笑
(ぶっちゃけ結構筋がわるくて参考にはならないと思ってるんですが、頑張った証跡として残します)

1日目 5/28(土)

12時からのコンテストだったので、やる気満々、12時に待機しました。
まずは恒例のFA狙いですが、出力例1をコピーしただけの提出はWAに終わりました。
長期コンテストは1度提出すると30分提出できないんですよね。
30分で問題の理解や、ビジュアライザを試したり、ローカル環境を整えたりを目指しました。
幸い問題自体の理解は難しくなくて、概要はこんな感じです

問題概要


こんな感じのスライドパズルを解きます。
もとの図柄は、全域木だそうです。
盤面の縦横のサイズ N は6～10で、 T=2 \times N^{3} 回までスライドできます。
N が 6 なら 432 回、 N が 10 なら 2000 回ぐらいの規模感ですね。
最終的にできた最大の木のサイズが全域木でなければ、サイズが大きいほどスコアが良く、全域木ならば、手数が少ないほどスコアが良いです
特に、ちょうど手数T をかけて全域木を完成させた場合はスコアが 500000になります。

ふむふむ。

正のスコア

とりあえず12:30になったので正のスコアを取っておきます。
空白が左端ならば右に1マス動かし、そうでなければ左に1マス動かします。完璧です。
→ WA
どうやら左右を間違えたようです (てへぺろ)
30分待ちます
左右をなおしてAC。
順位表を見ると、ほとんどの人たちよりスコアが低かったです
あとで知ったのですが、無を出力することでもACできて、そのほうがスコアが良かったようです。

7.92M

さて、30分待ってる間なにもしなかったわけではないです。
スコアを評価するのは難しくありません。
UnionFindで、連結成分の大きさを調べることができます。
とすれば、TL3秒の間ランダムに動かしてみて一番良いやつを採用しましょう。
ここで工夫としては、基本的には4方向からランダムなのですが、直前の動きを打ち消す方向には動かない、を入れました
例: L の直後に R に動かない ...など
これにより 7.92M点を得ました。

これは13:30頃の順位表ですが、なんと6位でした！
しかし1ページ目に居られたのは初日だけでしたね......

はい。
初日は結局そんなところで、次のとっかかりを探しながらハンバーグを食べに行ったり、昼寝をしたり、ABCに出たりしていたようです。

ABC

記事とは関係ないのですが、21時からABCに出ていました。
1級昇級をかけた大一番だったのですが、こけてしまいました...

気を取り直して次へ。

2日目 5/29(日)

8.99M

ABC後で日付がかわったので2日目のところに書きます。
スコアの評価がおかしかったので直しました。
連結成分のサイズを評価していたのですが、閉路になってしまうと「木」ではないので、閉路は計算に入れなくしました。
これにより スコアがちょっと伸びました。
就寝。

12.3M

さて、我々のような多くの社会人には土日しか休みがありません (この記事を書いている社会人の皮をかぶったゴリラも例外ではありません)
貴重な日曜日！ということでやる気に満ち溢れていました
ヒューリスティック問題を解くときに、ぼくの好きなアプローチがありまして、ヒューリスティックの名が示す通りヒューリスティックな関数を定義してヒューリスティックにやるのです。
これが大好きなんです。
何を言ってるかわからないと思うのですがこんなことをしました
これまでランダムな方向に動かしていたのですが、ある種の貪欲法というか、状態にペナルティをつけて、そのペナルティが減る方向へ動かします。
ペナルティは、隣接するマスのbit状態が異なれば1、としました。
たとえばこういうのは、左のマスから右へ線が伸びているが、右のマスから左へ線は伸びていないため、状態が異なり、ペナルティ1です。

こういうのは左右で繋がっているのでペナルティなしです。

これも左右ともに線が伸びていないのでペナルティなしです。
これの各行各列の境目について合計して全体のペナルティを決めます。
なお、盤面の端に向かって伸びている線もペナルティ1としました。

こういう貪欲はたいてい局所最適におちいって最後はループを繰り返すんですが、どうせ全域木はできないので手数は関係ないです。。
これを時間いっぱい回し、スコアの一番高いやつを採用です。

これにより 12.3Mのスコアを得ました。
さらっと書きましたが実装は地味に重かったです。(1手動かしてみて差分計算して戻して、、ペナルティが一番低いやつをえらぶ)

さて、このようなヒューリスティックな方法って最終的なスコアに生きたことがないんですよね...
遠回りとわかっているのですが、やりたくなってしまいました。

ARC

記事とは関係ないのですが、21時からARCに出ていました。
ARC苦手なわりに結果が案外良くて、昨日の冷えがチャラになったどころか、1級昇級までニアピンになります。

AHCとは関係なく、翌日が月曜なのに興奮してなかなか寝付けませんでした。

苦悩の日々のはじまり

さて、日記形式で書こうとしていて悲しいことに気づきました
結論から言うと、これ以降、最終日まで提出がありませんでした。
めちゃめちゃ苦戦してしまいました。

3日目 5/30(月)

眠かったみたいです。
先に完成図を作れるか？というのを考えていました。
つまり問題を2つに分けます。
完成図を見つけるパートと、完成図に向かってスライドしていくパートです。
完成図を見つけるパートは、適当な2マスを選び、swapを繰り返す焼きなましでできたりしないかなあ、などと考えていました。

4日目 5/31(火)

スライドパズルの解き方、けんちょん本2 (下記リンク) にありました。
パズルで鍛えるアルゴリズム力 | 大槻 兼資 |本 | 通販 | Amazon
ここにヒントがあるだろと思い読み返していました。
実際パズルを解くパートでかなり役立ちました。
IDDFS や IDA* といった手法も紹介されていましたが、 N \ge 6 の規模ではさすがに3秒で解けないだろうと思い断念しました。

パズルをある状態まで並び替えるときに、上から1段目をそろえて、2段目をそろえて、...N-2段目をそろえて、次に左から1列目をそろえて、2列目をそろえて... とやると良さそうと分かりました。
これを実装することを考えていくと、少なくとも「あるタイルを目標とする位置へ動かす」という操作が必要になります。
下の図で、「A」というタイルを1つ左に動かすのには、DLLUR の 5手組の操作をすると良さそうです。

3つ左に動かす場合はこれを3回繰り返せば良く、また上に動かす場合は RUULD などと向きを変えれば良さそうです。

なんとなく、パズルを解くイメージが湧いたところで、1つ懸念が上がりました。
仮に全域木が焼きなましで見つかったとして、それを完成させるのに T=2 \times N^{3} よりも手数がかかりすぎてしまうのではないか？という懸念です。
すごく雑に見積もると、 N \times N 個タイルがあって、それぞれ最終的な完成図から Nマス離れていたときに、5手組の操作を N^{3} 回するので、 5 \times N^{3} 回の操作が要るのではないか？
しかもこれに加えて、動かしたいタイルの真横まで空きマスを動かすターン数もかかります。
これだと到底、揃えることができません。
完成図を見つけるパートと、完成図に向かってスライドしていくパートに分けたところで、スライドさせるパートで半分も完成しないのでは、あまりにお粗末です。
方針転換が必要です。

テストケースの生成方法に注目してみました。
要は、ランダムな全域木を生成したあとに、 T=2 \times N^{3} 回ランダムに動かして生成していると。
T=2 \times N^{3} 手で完成するのが保証されているのはもちろん、これだけのランダムムーブでは各タイルは元の位置からさほど動いてないものが多いのではないか？と考えました。
焼きなましをする際、適当な2タイルを選んでswapを考えていたのですが、これだと完成させるのに手数がかかりすぎてしまうと思い、これをやめて適当な1タイルを選んで8近傍とswapし続けることにしました。

とりあえずそんな方針で焼きなましを書きました。
近傍swapしたあとに全体をUnionFindで評価しなおしているので、無駄が多いかもな (というかUndo付きのUnionFindを使うべきかな) と考えたのですが、とりあえず αN^{2} のオーダーなのでひとまず許容しました。。
ちなみに焼きなましを書いたのは今回が2回目なのですが、もうばっちりでした。

↑初めて書いた焼きなましは去年の AHC006。じじいさんのおかげです。

温度とかのパラメータは手元で100ケースぐらい回し、を繰り返しつつ、良さそうなのを適当に決めました。
すると、全域木とまではいかないまでも平均的に 8割程度の全域木 ができました。

↑この頃はうまく動いたので、たのしい～～、という感情でした
この後に地獄が待っているとは知らずに...

5日目 6/1(水)

実装にハマっていたようです。
とりあえず焼きなましの精度を上げる必要もありますが、パズルを解くパートが完成しないことにはスコアも伸びないなと思っていたのでパズルを解くパートを頑張っていました


さっそくナイーブな気持ちになります。

6日目 6/2(木)

あと3日を切って泣きそうになっていたようです。

しかし体調が悪かったのでこの日は早めに休みました。

7日目 6/3(金)

とんでもない誤算を見つけてしまいます。

これは何かというと、ジャッジのテストケースが50ケースだったのを100ケースだと勘違いしていました
上位陣はすでに40Mほどのスコアをたたき出していましたが、ぼくはこの解釈を「全ケースで全域木を完成させてる人はまだ存在してない」と思っていました。
いやいや、彼らは「全ケースで全域木を完成させる」なんていう次元はとうに超えていて、すでにTの半分以下の手数で 手数を削る戦いをしていたのです！！
自分の状況はというと、焼きなましは8割全域木だし、パズルパートはまだ書けてなくて手数もTで足りないかもというレベルで、これでも全域木の6割の盤面ができるならば スコアは300000 の 100倍で 30M出るな、などとのんきなことを考えていました。
見積もりを改めなければ。
平均的に全域木の6割ができるならば 15M。現状からちょっと伸びた程度。
焼きなましで作った8割全域木が T ターン以内に解けたとしても、20M。
つまり現状の手札では、どんなに良くても20Mしか行かないのでは... と悟りました
ここまで苦戦を強いられていたとは。
しかし、他にアイデアもないし、とにかくパズルパートを完成させよう、そしてその先に何かが見えるかもしれない...
と信じて進むことにしました。
目標は漠然と30Mだったのですが、20M行けば良いだろうと、下方修正しました。

8日目 6/4(土)

ツイッターを見る限り、金曜は27:30 まで起きていたようです
が、待ちに待った土曜。気合を入れる。
パズルパートの実装にあたって、この手のルールベースは実装が地獄になりがちなので、一旦ホワイトボードなどを使って整理することにしました
1つ嬉しい性質に気づきました。
「A」というタイルを1つ上、1つ左のマスに動かしたいとします。
下のように、ULDLUR と動かすと、6手で「A」を2マス動かせます。

1マスあたり5手組の操作が必要と思っていたので、うまく動かす順番を工夫すれば1マスあたり3手になるのは、嬉しいです。
嬉しいっちゃ嬉しいのですが、動かしたいタイルと動かす先のタイルの位置関係によって、施策が変わるのは、実装がごちゃごちゃします。

これらを一般化する実装を考えました。
中の実装は省きますが、こういう関数を書きました。

def move_space_to_any(targets, to_avoids):
   # 多点bfsみたいな実装

空白マスを targets のいずれかに最も近づくように1マス移動させる、ただし to_avoids は踏まない
これを呼び出すとき、targets は動かしたいタイルに隣接するマスで、かつ動かす目的の方向と合っているものを指定します。
例えば「A」というタイルを左上の方向に動かしたいとき、とにかく「A」を左か上に動かしたいので、「A」の真左か真上に空白を持っていくことで、次の手で「A」を目的の方向に移動できるようになります。
(そのうち図を描きたい... (けどこれは描かないパターン><))
to_avoids には、すでに位置を確定させた (動かしたくない) タイルのリストを入れます。
詳細は省きますが、これを使うことで、6手で2手動かすのも、5手で1方向に1手動かすのも、区別のないコードで書くことができました！

末尾のつじつま合わせ

ところで、一番上段が 1 2 3 4 6 5 のように揃っているとき、 1 2 3 4 5 6 に直すのがかなり大変でした。

手でこの状態を解消してみたところ、17手かかりそうとわかりました。
私が見つけたのは 5 の真下に空白マスがある状態から、 ULDDRULURDDLURULD とやるととりあえず揃います^^;;
もっと良い方法があるかもしれません。
こういったケースなんかもコードに埋め込んでいます。

長いコードを書くとき、途中で「ありえない状態」になってないかを検知するため、assert 文をよく埋め込んでいるのですが、手元で100ケース回すと、いろんな場所で assert にかかっていて、要はバグり散らかしていた んですね。
残り24時間を切って、この状況、もうダメかも... なんて思ったりしました。

ABC

記事とは関係ないのですが、むしろこちらが本編という説があるのですが、21時からABCに出ていました。
現レート1799、レートが伸びれば1級昇級、伸びなければしばらくお預けの大一番でした。
結果としては大成功して、初の1800台、1級昇級を果たしました！

アルゴ青に到達してから3年半も彷徨っていたのですね。
何度水色に叩き落されたことやら... (12回のようです)
感涙。そして興奮。

最終日 6/5(日)

さて、ABCの興奮も冷めやらぬままに、まだまだやることがあります。
AHCの終了は19時です。
まずは目の前のバグ (先ほど見た大量に引っかかる assert ！) を解消せねばなりません。
ここはもう根性です。
ゴリは1級アルゴリズマーだぞという誇りを胸に戦います。

このようなケースで引っかかっていました
(あとで図をいれる)
(と書いてありましたがこれを編集してる今は8月でもう覚えていません...><)

14.7M

バグ取りをしてたら鳥がチュンチュン鳴き始めて、頭がおかしくなったようです。
気合と根性で、すべてのassert を取りました！
手元100ケースでも引っかからない。
上から N-2 行までを揃えるコードを書きました！
(実は下2行はまだ)
提出。14.7Mのスコアを得ました。
提出時刻は5:49。朝ですね。やっと眠れる。

15.6M

10時におきました。
普段7時間は絶対寝るんですが今日は4時間です。
カラダ持ってくれよ！！
というわけでやることがたくさんあります。
ひとまず、現状のコードは上から N-2 行までを揃えてみて、Tターンを超えていたらT文字で切る、という実装がされていました。
生成された操作列を最後まで終えた時がスコアの最大値ではなく、操作列の途中でスコアが極大になる可能性もあるなと思い、操作列ができた後に操作列のprefixを全部評価するようにしました。
オーダーは αN^{2}T ぐらいでボトルネックにはならないのでokです。
これにより 15.6Mのスコアを得ました。

17.7M

未実装となっていた下2行を左から揃えるパートを実装しました。
これにより 17.7Mのスコアを得ました。
結果的には上から揃えるやつのコードをほぼほぼ流用できたのでよかったですが、それでもタイルが逆転したときの解消が厄介で、結構時間を要しました。
あと、最後に残った2×2マスは、幅優先とかでも良かったのですが、時間がなかったので実装をサボって空白マスをぐるぐる回すだけにしました。
スライドパズルはそもそもパリティが合わないと絶対に揃わないという性質があるのですが、そこは割り切って右下の端がちょっと欠けても良いだろうぐらいに考えて、気にしませんでした。(詰めが甘い)

ちなみに、このときにseed=0 を共有していたのですが、これはうまく揃ったときのやつで、そもそもまだ焼きなましの結果は平均で全域木の8割程度だったので、本当に何を食ったら揃うのかわからん ってレベルでした。
それでもビジュアライザでこれだけ揃ったのは初めてだったので、ちょっとうれしかったです。
ちなみにこの日は 味の民芸の豚生姜焼き弁当を出前していたようです。

ボツ実装

残り7時間となりました。最後まで戦い抜きます。
焼きなましの評価のしかたにマイナーアップデートをしましたがいまいちでした。
どれぐらい連結してるか、みたいな指標をいれてみたようです。

22.0M

ここで大きな無駄を省くことに成功します。
現状は、焼きなましで作る完成図は8割ぐらい、ルールベースでそれを目指してスライドするパートも手数がかかりすぎて最後まで完成しない、って状況でした。
なにが無駄だったかというと、完成図のデータの持ち方です。
これまでは、各タイルをswapしていくときに、そのタイルが最初にどこにいたか を持っていました。
そして、焼きなましで完成図を作ったあとに、完成図の各タイルが最初にいた場所のタイルを律儀にその場所にスライドさせようとしていました。
これは大きな無駄があります。
タイルは15種類しかなくて、種類の出現数に偏りもありますが、同じ種類のタイルはたくさんあります
同じ種類のタイルは同一視したほうがよかった のです！
どこに最初にいたかは関係なく、最寄りのほしい形のタイルをスライドして持ってくる戦法にしました。
これで、手数には割と余裕をもって、焼きなましの完成図通りにスライドできるようになりました！
これで22.0M！
よくて20M、の見積もりだったので、少しほっとしました。

24.8M

焼きなましを改善したくなりました
タイルがもといた場所が重要ととらえていたので、隣接swapしかしてなかったのを、任意の2点をswapするようにしました。
感触はかなり良さそう！


何食ったら揃うか分からなかった全域木も、初めて完成しました！！
22.0M → 24.8M です！！
このとき、終了3時間前にせまっていました！
ありがとう豚生姜焼き弁当！

悪あがき

あと3時間となるとそんなに大きな改修はできません。
手ごろに伸ばせそうなところを考えます。
16:45 の提出では焼きなます前になにかしらの貪欲で配置してから始めることにしましたが、24.4Mで伸びず。
17:15 の提出で添字ミスを見つけて直すも、これも24.45M で意味なし。
18:00 の提出はもはやメモが残ってなくてなにをいじったか分からない。24.3M。
もとのコードに戻します。

最終提出

ラスト1時間は焼きなましのパラメータを色々いじってローカルで改善したやつを投げることをしました
意外と改善があって、 26.7M までいけました！！

記念のGIFも貼ります。意図通りに動いてくれてピッタリ揃う様子が動画で見れるの、気持ちいいですね！！

まとめ

システス後の結果は少し下がりましたが、153位でした。

全体的につらい戦いでしたが、最終日は根性でかなり追い上げました！
アルゴで1級昇級！をこの時期にできたのも根性を後押ししてたような気がします！
いつもながら充実した日々を過ごせていたと思います！
ありがとうございました！！

反省

コンテスト終わってから2か月経っているのですが！？！？
記事を書くなら忘れないうちに書きましょう

明日から

AHC013 始まりますね！！
またこのときみたく根性が出せるかわかりませんが盛り上げていきましょう！！