1.はじめに
制限時間4時間の短期コンテストは決勝コンを除けば、AHC021(6月頃)以来なので久々ですね
今回は開始前に意識しようと考えていたことを事前に書いておきます
・問題文をよく読む 制約をよく読む
→おそらく一番大事です。特に厳しい側に制約を勘違いしていると、全然スコアが伸びずに終わってからガッカリすることになります(AHC021でやらかしました)
・強い貪欲を考える(順位表も参考に)
→多くの人が同じことをすると思いますが、だからこそ強い貪欲解法に気付けていないといくら工夫しても伸びないように思います
・考えに詰まったら紙に書いて整理or少し歩く
→気分を変えたりすると急にアイディアが出てきたりするので、短期とはいえ1時間に1度くらいはリフレッシュをするようにします
2.問題
問題文を要約すると、
・色分けされている地図の隣接関係を保持したまま小さく圧縮せよ
実装中に気を付けないといけないポイントとしては、以下の２つ
・地図の中に空白(白マス)があってはいけない
・同じ色が離れ小島になってはいけない
3.解法
思いついて実装できた順に書いていきます
・周囲を白マスで埋める
これだけではスコアはほぼ出ませんが、これを実現するためには、
正しい提出をするためのチェック関数が必要で、それをこの後も使いまわせたのは良かったなと思います
正しい提出をするためには、以下の２つが必要です
・各色が連結であること
・各色の隣接関係が保たれていること
「各色が連結であること」は、bfsで探索して別のタイミングでもその色が出てきたら連結でない。とみなしていました
「各色の隣接関係が保たれていること」は、隣接色のリスト(set())で持っておいて、変更前後で一致するかチェックしました
最初壁に接している箇所は、空白マスとも接している必要があります
上記２つのチェックを、O(N^2)で判定しているので非常に遅いです
より高速な判定を他の方はしているはずなので勉強します
・縦、横に切断して詰める
開始1時間くらいで思いついてこれはいけそうだなと思いました
いつかのAHCで、ケーキを縦横に切る問題があってそれをイメージしました
この時点で本番130位相当のスコアが出ました
・中途半端な長さで切断してみる
前述の方法では、1列or1行がすべて消せないと実施できないため、切断長さにランダムさを加えてみたところ、少しスコアが向上しました
・飛び出ている所を均す
切断していく解法の都合上、1マスだけ飛び出ている箇所が邪魔に見えたのでその箇所を周りの色に変える処理を入れました
処理としては、自身の周囲4マスを見て丁度3箇所が自身と違う色なら、周囲で一番多い色に変えています
最初に強めに(n=5回)均して、後は250回に1回程度の頻度で均していました
・最後に、消して良い箇所を空白にする
最初に書いたことと同じ意味になりますが、切断フェーズ終了後に空白マスと隣接しているマスを消してみて、問題ないか確認する処理をしました
ここの処理で何秒かかるか不確定なため、切断フェーズを少し早めに切り上げています(開始から1.7秒で中断)
・1マスだけの色を隣に増やす
ビジュアライザを見た時に、1マスだけの色を含む行列に関しては確実に切れないことに気付き、増やせる方向があれば増やす処理を入れました
次の案がこれの代替になると途中で気付いて、この処理は最終的には使っていません
・ランダムに1色変更する
色のついているマスをランダムに選んで、その周囲4マスで変更できるマスがあれば自身と同じ色に変更します
切断のネックになっている箇所は、1マス色の箇所だけとは限らないためこの工夫は割と効きました
この処理は、切断処理を試して切断できなかった時に実行しています
4.最終提出のビジュアライズ
行列方向に切っては詰めて、切っては詰めてをした様子
— uta (@uta_cccc) 2023年9月24日
切れなかった時に、適当な場所の色を一つ変えていました#AHC024 pic.twitter.com/BBO8b7YAhk
5.提出コード
PyPy3で書いています
気付き、ダメ出しなどあれば言ってもらえると喜びます
6.終わりに
4時間の短期コンテストは、思いつかなかったら爆死のイメージがありましたが、今回は思いつけた側になれたようで、27位の黄パフォを初めて獲ることが出来ました！
10/14~長期コンがまたあるので、そちらも頑張りたいです
以上、読んでいただけた方ありがとうございました
