AHC024 解説
丸紅プログラミングコンテスト2023（AtCoder Heuristic Contest 024） のコンテスト中 & 後に考えたこと、あと提出での改善内容について書いています。
286,416点で91位相当の解法になります。
方針立て
問題文を読んだところ、ざっくりと思いついた方針は2つで、
0で埋めたマップに一番数が少ない色を圧縮した形でおき、その周りの色をなるべく圧縮しておいていく。「なるべく」の部分がどうすればいいかわからない。
周りから圧縮していく(0に置き換えていく)。内側の色をどのようにして圧縮していくのかわからない。
と、実際にはどうしていいかわからない状態でした。
ただ感覚としては「強い人は焼きなましでやりそうな問題ぽい」と感じたので、一括で盤面を小さくする1より、条件を満たしたまま徐々に小さくできそうな方針2を選ぶことにしました。
さて、問題は2の方針でどうやって内側の色を圧縮していくかです。
外側については0と接しているので、0に置き換えられるものは置き換えていけばいいだけです。それなら内側の色を外側に接している色に置き換えていって、外側の色を0に置き換えていくバケツリレーみたいな形でできないかと思い、そのように実装しました。
ここで内側、外側をどう定義するかですが、一番外側の色は0でいいです。あとはBFSみたいな要領で、
0を外側とする。
外側に接している色で、まだ使っていない色を内側とする。内側を外側の色の種類数を開始値として連番で適当に番号付けする
2で内側としたものを外側として追加する。2に戻る。
と番号付けしたものを優先度として、優先度が低い方がより外側にあるとしました。
これで内側と外側が定義できたので、
色が0以外のマスを1つ選び、
そのマスに別の色の外側がある場合、外側の色で置き換えられるか調べ
置き換えられるようなら置き換える
ということをしました。3の置き換えられるようなら、というのは
置き換えられる側の色の連結が保たれる
置き換えられる側の色が接している色の種類・数が変わらない
置き換える側の色が接している色の種類・数が変わらない
です。連結性はUnionFindで、色Aが他の色に接しているかどうかはRustのu128をBitSetのように使って管理しました。
改善フェーズ
方針立てのところを基本にして、それから改善した点について書いていきます。
■色を置き換える際、優先度を無視する
実際に方針通りにやったところ、圧縮結果がウニみたいな感じになっていました。
最終解法のGIFで、伸びている部分がより多くて悪化した感じになっていました。
こういう状態はランダム要素がなく(もしくは乏しく)、特定の状態に同じ処理を繰り返すため(もしくは高確率で同じ処理を繰り返すため)、状態が改善できない状態にあると理解して優先度を取り除きました。
具体的には色を置き換える際、隣接している別の色をランダムに選び、その色で置き換えられる場合は置き換えるようにしました。
実際かなりきいて、172,751点 $${\rightarrow}$$ 285,543点になりました。
ただ、改善フェーズに着手するまで3時間使って残り1時間という状態だったため、他は乱数上振れ頼みの提出しかできませんでした。
最終解法
seed1の結果のgifを載せます。
ここからどうするか
GIFを見ても分かる通り、まだまだ無駄に伸びている箇所があります。原因は「0を他の色に置き換える処理を入れなかったから」です(スコアが下がる方向は許容しないようにした)。
コンテスト中は方針立ての方に書いている、「置き換えられるようなら」のチェックに時間が結構かかると踏んでいて、「0を他の色に置き換える処理を入れる余裕はない」と判断したためです。
実際はGIFを見れば分かる通り割と早い段階で収束しているのですが、計算量的には余裕で収束するとは言えない感じだったので(実際ある程度収束するのに数100msecかかっている)、焼きなましより山登りっぽくしました。
ここからは
イテレーションをたくさん回すための処理の高速化に「周囲8マスを使っての連結性チェック」を導入する
スコアが下がるような処理も入れる
あたりの対応をすることになります。時間が足りない。。。