【AHC024】 19位解法 - milkcoffeeのブログ

AtCoder Heuristic Contest 024 で 19位を取ることが出来ました。

順位表の1ページ目に載るのはアルゴ部門含めても初めてのことで嬉しいです。

記念に書いてみたかった解説記事を書こうと思います。

最終提出のビジュアライザは以下の通りです。

seed : 0 で 1935点です。

提出したコードのアルゴリズムは以下の通りです。

以下に詳細や実装方法などを書きます。

位置関係を保ったまま大きい区画を縮めたくなり、この操作を思いつきました。

実装としてはマスが存在する全ての列において以下を行ってます (行も同様)。

削除は行と列で交互に行って「1行目、1列目、2行目、2列目・・・」みたいに見ています(これが良いかどうかは怪しい)。

また、条件を満たすかどうかの判定は高速化は特にせず、 O(N^2) で行っています。

seed:0 でこれを 1 周すると以下のようになります。これだけでも 1000 点超えます。

行・列の削除をより行えるようにするためには、盤面に変化を加えたいです。

そのために隣接するマスの色に置き換えることを行います。

削除できる行・列が無くなるたびに、以下の操作を1000回行います。

ランダムに(空白でない)マスを選び、それと隣接するマスの色に置き換える。
- 隣接する色も同じ色だった場合は置き換えずスルーする。
- 隣接するマスが空白の場合、実行時間が 1 sec 未満ならばスルーする。
置き換えた結果、条件を満たさなくなったら元に戻す。

seed:0 で実験したところ 1000 回がちょうど良かったので1000回にしています。

「隣接するマスが空白の場合、実行時間が 1 sec 未満ならばスルー」というのは、早い段階で空白マスへの置き換えを許容してしまうことで削除できた行ができなくなったりするため入れた処理です。

ここでの条件を満たすかの判定も高速化していません (ここは流石にした方が良かった)

隣接マスの色に置き換える処理を入れたことにより、削除できる行・列が増え、よりスコアが伸びました。

時間いっぱい 1 と 2 を繰り返します。

高速化をしていないため、ここのループは20回ほどしか回っていません。

外側の無駄な土地をできるだけ空白にします。

賢い方法が思いつかなかったので、以下の処理を2回行っています。

これらを実装した結果が以下のビジュアライザになります。(最初に載せたものと同じ)

やったけど上手く行かずに不採用 or 思いついたけどやらなかった、やれなかったことのまとめです。

問題を見た瞬間にこれは楽しそうだなと思って、実際に楽しみながら良い順位を取ることができたので良かったです。

考察については、行・列の削除という操作が早めに思いついてそこからスムーズに進んみました。上位の方と方針がわりと似ていて、あたり方針を引くことが出来きたなと思います。

実装についても、途中参加でかなり焦りながら実装していましたが、特にバグらせずに実装し続けることができ、自分にとってはかなり調子が良かったと思っています。

また、今回でついにアルゴのレート (highest:2104) をマラソンのレートが超えました。

橙になりたいけど橙パフォはまだ安定する気がしていないので、かなり遠そうだなと思っています。

AHC は楽しいのでこれからも頑張っていきます。現在就活生ですが、ヒューリスティックや最適化をやっている会社も良いなぁという気持ちになっています。

記事は以上になります。ありがとうございました。