AHC11参加記 「緑コーダーの山登り法による17M点解法」
あいねむと申します。 長期AHCが大好きで、色んな方に取り組んでもらいたい気持ちがあり、少しでもハードルを下げられたらと思い、誠に僭越ながら解説記事を書かせていただきます。
問題
ざっっっくり説明すると、16種類のピースがあるスライドパズルを動かしてできるだけ大きな(=頂点数の多い)木を作ろう！
もし全てのピースをつなぐ木を作った場合、作った早さも得点になるぞ！
最初に浮かんだアイデア
①山登り
空きマスを上下左右に1マス動かすことを1操作と考えると、1操作だけではスコア（盤面がもつ最大の木）が変化しないことが多い
7操作ぐらいずつランダムで動かすルートを100個ぐらい列挙し、木が大きくなるものを選ぶ。(貪欲法)
評価関数がどれだけ遅いか？時間ぎりぎりまで探索する。時間たりなさそうなら盤面を分割して考える？
②自由に操作
例えば葉を外にとか、例えば理想の木を作るとかの目標を決めて、その盤面への操作を求めるまず理想の木を作れる気がしない、そしてその盤面への操作もできる気がしない… ABC224D(うにだよさん解説)を読むも、これが最大100マスあるとなると計算量が爆発するどころじゃない…宇宙爆発待ったなし…
ということで
まずは①山登りの方針で実装してみることにした。
実装
実装が重いことが参加のハードルとなっている可能性があるな、と思いましたのでかなり詳細にgoogle colab上で説明しました。
リンク先の「Open in Colab」から、実際に実行できるはず、、、です！
この記事のメインコンテンツのつもりです。DFSが書けるレベルであれば、理解できるんじゃないかと思います。是非Twitterとかで質問してください！
スコアが改善したもの
【WA】満を持しての初提出
WA！！ひゃっほい！（ターン制限を全く考えていなかった）
【13668040】正の得点GET
Submission #32126657 - AtCoder Heuristic Contest 011
T以上になった時ループを中断するようにして、2回目の提出で正の得点ゲットだぜ！
【13668040 -> 15377134】往復移動を無くした
Submission #32136371 - AtCoder Heuristic Contest 011 ルートを作る際、LRLRLRLR..などの往復移動も候補にあげていたので、元いた場所に戻るルートは作らないようにしました
【15377134 -> 15614987】 木の破壊の許可/非許可のルートを作るようにした
Submission #32139580 - AtCoder Heuristic Contest 011
木の破壊を許可しない、つまり最大の木の頂点を記録して、そこは通らないルートを作るようにしたら、いわゆる局所解にはまった、最大の木に閉じ込められて動けない状態になりスコア改善しなくなった
候補のルートのうち半分を木の破壊を許可、もう半分を木の破壊を許さないルートにして、そのうちスコアがもっともいいものを選ぶようにした
でも、これは最終的には木の破壊を許可するルートだけにした方がスコアがあがった
おそらく、乱数のブレだったんだろう…
【15614987 -> 16401198】 二次元配列を一次元にした
Submission #32154320 - AtCoder Heuristic Contest 011
ありがとう、ゆうさんろんどんさん…
ちょっと日曜までは詳しく言えないんですが、AHC、ゆうさんのおかげでものすごく助かりました！！ありがとうございます！
— ainem (@ainemixion) 2022年6月2日
matrix[x][y] -> matrix[10*x + y]に変更した (ほんとは[N*x + y]なんだけどメモリ使用量に大きな影響なさそうだし、見やすい10倍にした)
【16401198 -> 17384415】ルートの評価
Submission #32191011 - AtCoder Heuristic Contest 011
今まではルートの評価は移動後の盤面の状態だけだったが、ルート自体の評価もするようにした 最後の方、木に囲まれてぐるぐるしがちなので移動の範囲の大きさを評価に入れてみた
この提出を何度も行い、50万点ぐらいの振れ幅があることに気づいた！これは今までの改善の幅ぐらいある…笑 次回からはランダムのシードを固定(note.nkmk.me)して改善したかどうかはっきりさせようと思った
スコアの改善がなかったか、実装に至らなかったもの
ハイパラ調整
ROOT_LENGTH(一度に移動する量) TEST_TIME(ルート候補をつくる量) の値をいじっても、スコアは大きくは改善しなかった iPhoneからでもパラメータ調整はできるので実装の時間とれるときにやる必要なし もう何も浮かばないけど時間はある最終日にはやってもいいかも、でもやるとしたら大量のテストケースが必要 randam.seedを使ってseed値を固定していじらないと意味がない！！
前処理の関数を作る
例えば空きマスを最初に真ん中に寄せるとか まだ実装できないけど葉を端に寄せておくとか 空きマスを寄せるのだけ帰ってからサクッと実装してみたが、ダメ きっと他のアイデアと組み合わせなければ意味がないものなんだろう…
参考にしたもの
診断人さんの焼きなまし法のコツ Ver. 1.3を大変に参考にさせていただきました。百回読みました。
困ったこと
M1Macの罠
ローカルテスタ、全然提出の点数と連動しなくて困っていましたが、ローカルではPythonで回していて、提出はPyPyで回していたので、そのせいでローカルだと全然点数が伸びない、ということが起きていた
よし、じゃあPyPy入れちゃうかーとなりますが、PyPyはM1Macに対応していない（驚愕）
長期AHCだけ他言語使うことを本気で考えた(N回目)
焼きなましたい！
山登りだとおそらく限界がある、焼きなましできる遷移を見つけたい、と日記に毎日書いてあった（笑） 山登りには限界がありそう(上位陣みんな25Mを超えてる→制限ターン以内に木を完成させてる) 今回の方針で焼きなましするには、少しの変更でスコアが下がりすぎる(今までの木を壊してしまう) 焼き鈍し法（状態：盤面 次の状態：ランダムなルート スコア：最大の木の大きさ）をやってみたが、試行回数を増やすために操作回数制限がボトルネックになり、おそらく時間制限前にルート確定してしまい、うまく行かなかった、この遷移だと前半はスコアが上がらないのが当たり前で、後半は大幅にスコアが下がりやすいのであんまり意味がなさそう ツカモさんの記事で言う焼きなまししにくい構造になっていそう
上位陣(現人神たち)の解法をみてびっくり、まさか完成図の方を焼きなましするとは！！たしかに、近傍を作ることができそう。いつか実装してみたい…
振り返り
結果的に最初に思いついたアイデアを改善し続ける形になった 25Mの壁（完成形を作れたかどうか）には気づいていたが、どうしても実装できる気がしなかった 焼き鈍し法の気持ちが少しだけ理解できた（どんなふうにうまくいかないか）
日記の大事さに気づけた。日記を記録せず/読み返さずに熱烈実装！をしていたときはスコアの上昇がほぼなかった 実装しながら考える は私にとっては愚行のようだった。
脳内イメージはあくまでもやもやっとした曖昧なイメージなので、実装に落とし込むには粗すぎる…脳内イメージで完璧に整理がついた、と思った概念をシェーマを書いたり文章で説明しようとするとつまるところがたくさんある。実装はかなり精密な作業なので、いきなり実装、は天才の所業
そんなことわかってはいるんだけどいざ実際、順位表とかツイッタとかビジュアライザを見ると早く提出したい焦りに勝てなくなる…
コメントも大事！！３０分前の自分が何を意図して書いたのかわからないことが多発。コードはあとから微調整がきかない（絡み合っている）意図がわかれば改変もしやすい。むしろ改変しやすい構造で最初から書くのが大事。リーダブルコード読み返そうと思った。 型ヒントは便利 変数名の他にもう一つ情報が増える、しかもエディタにチェックしてもらえる！
でもPythonの場合List[int]とか書くためにはジェネリック型？とかが必要でimportしなきゃないからめんどくさいよね…
Pythonの限界を感じた 手元でテストを実行するときに遅い、コードをわかりやすくするために、たとえば座標などの簡単なものを構造体代わりにクラスで書いたりすると遅くなったりする。
みなさんも是非、私のコードを写経、改変でもいいのでまずは提出してみてください、そしてAHCの喜びを分かち合いましょう！
徹頭徹尾、竜頭蛇尾。
