RECRUIT 日本橋ハーフマラソン 2022夏(AtCoder Heuristic Contest 013)
1週間 + α の長期ヒューリスティックコンテストですね!
今回、有効な手立てを筋道立ててできたわけではないのですが「色々やろうぜ」ってやった結果そこそこスコアを伸ばすことができてとても満足しました。最終 222,681点、暫定129位と順位も悪くないです。
問題
K種類のコンピュータが100台ずつ、N * N の正方形盤面に配置されている。
コンピュータを移動させた後、接続していい感じのクラスタを作ってください。
クラスタは1種類のコンピュータをたくさん繋げると最高で、他の種類のものが混ざると弱くなります。移動・接続できる回数には制限があります。
https://scrapbox.io/files/62fb8e4b4b3fc2001db02635.png
考えたこと
操作回数の制限が K*100 なので、結構厳しい。
K=2 みたいなケースだと移動をやってる余裕があまりなさそう
1種類のコンピュータを最大まで繋ぐことを優先するのが効率良さそう。
クラスタの評価は同種類のコンピュータ台数の2乗に近いので
コンピュータを混ぜない方向なら、接続はBFSで楽に実装できそう
やったこと
初日 (30,000点)
接続に関する実装は最終まで無駄にならないはずなので、接続を実装した。
移動を全く考えない感じで雑に実装して、初回提出を済ませた。
1, 2, 3, 4, 5 の順番で接続をしてたのだけど、これだと無駄があるかもしれないので全ての並び替えパターンで試すバリエーションとかを実装した。あまり改善しなかった。
2, 3日目
労働したり飲み会したりの影響で大した進捗はなし。
まともに使えるレベルのスコア計算機を実装した。
訪問ずみフラグと Union-Find を併用した実装でコードが汚くなっていく。
公式による Rust のものと結果が一致することを確認するなどした。
4日目 (30,000 => 80,000点)
移動を考えてみる。同じ行・列に同種のコンピュータが集まっていると嬉しいはず。なので、1マス移動させて集められるやつを集める感じの実装をしてみた。65,000点。
接続についても改善の目がある。種類ごとの順番で、ではなく「大きいクラスタが組めそうな順番で」という感じの貪欲さを組み込んでみた。約80,000点。
5日目 (80,000点 => 92,000点)
接続をする際に「1つだけ他のコンピュータを混ぜて拡大できる」ケースがいくつか見られたので、これを実装してみる。
混ぜすぎるとスコアが減っていくので、とりあえず1つだけ混ぜるのを雑な実装でやっていく。
考えは簡単で、BFSの時に他のコンピュータが壁になったやつの座標を記録しておく。その後、探索状態をリセットして、壁を同種のコンピュータとみなして再探索する、というのを1点ずつ繰り返していく。途中バグらせながらもなんとか実装した。92,000 点。
6日目 (92,000点 => 100,000点)
移動について焼きなましの試作をしてみる。空白の点をベースに上下左右に何回か動かしてスコア計算をする、みたいな形。スコア計算を毎回やってるせいか回数が全然回らない。空白が多いケースでは遅すぎて使い物にならなかったので、空白が少ないケースだけ動くようにして提出してみた。これでなんとか100,000点を超える。
100,000点に乗ったことでかなり満足する。
7日目 (100,000点 => 174,000点)
スコアの計算を一部簡略化することで焼きなましの実用に耐える速度にできた。それでも十分に回る感じではないが「焼けている」感じはする。
目に見えてスコアが改善していて素晴らしい。174,000点。こんなに効果が出るとは思わなかった。
ヒューリスティックで良くやる「xミリ秒経ったら終わり」みたいな実装を今回初めて実装した。便利だし安心感があって良い。これまではループの定数を頑張って調整するという緊張感がある雑な仕事をしていた・・
8日目 / 最終日 (174,000点 => 220,000点)
焼きなましの回数を稼ぎたいので、処理の高速化を地道に頑張る。
焼く時のランダム要素も結構テキトーに実装してたので、いい感じにする。
スコア計算は盤面全体をやるのではなく、稼ぎ頭になりそうな 1, 2 個のクラスタ分だけをやることで大幅に簡略化できてかなり速くなった。これで計算時間に余裕ができた。
移動は「残り操作回数が100になるまで」という最終条件で回していたのだけど、これまでは焼きなましが遅くてそこに到達しなかった。今回そこに届くようになった。
こういう場合、最後の方の移動は無視して接続を優先した方がスコアが伸びるケースがありそう。なので、移動をちょっとずつ減らして一番いいスコアの時のやつを出力する、みたいな実装も加えた。
最終結果
システムテストが終わるまで待ちです。落ちないでくれ〜〜〜〜〜〜〜〜
落ちませんでした!最終順位は121位でした!
もっとやりたかったこと
seed=7 みたいな「種類が多く、空白が極端に少ない」ケースの稼ぎ。例えば、序盤に1種類のコンピュータを雑に寄せてから焼きなましをする感じにすれば改善できるのではないかと思った。ただ「寄せる」って簡単に書くけど難しいんだよな。
焼きなましの手数の拡大。今回は最大3マス分の移動だけを実装していたけど、空白がとても多いケースだとブレが大きかった。
接続の実装で、2つ以上別種類のコンピュータを混ぜるのをやりたかった。1つ混ぜるだけでも複雑な実装になってしまったので、ここを拡張するのは骨が折れそうだった。設計力に課題を感じる。
接続の実装をもっと速くする。1盤面ごとに50msくらいかかる雑実装をしていたので良くなかった。