AtCoder Heauristic Cotest 014 解説(9位)
日記はこちらです↓
penguin46.hatenablog.com
結果
pretest 、システムテストともに9位
問題概要
格子点上に頂点を1つ追加して軸に平行or45度傾いた長方形を作ることを沢山繰り返してください。既存の頂点を通ったり、辺を共有するような長方形は追加できません。
解法
一部の長方形を削除して貪欲で再構築する焼きなましをしました。長方形を削除すると宙ぶらりんになる長方形が生まれるので、それらも削除します。*1
長方形の全列挙
各頂点から8方向に線形探索し、直角な2方向で別の頂点に到達したら、その3点を使う長方形が作成可能かを判定することで全列挙します*2。長方形を追加すると、新たに作成可能になる長方形が生まれるので、追加した頂点を使う長方形を同様の方法で探します。ちなみに作成不可能になる長方形も生まれますが、この判定は必ずしも必要ではないので、評価値が高く使用したくなった時に遅延評価するようにしています。
貪欲パート
作成可能な長方形をから、評価値が高いものから使用していきます。使用する評価関数は1回の貪欲につき下記の2つの内1つをランダムに選択します。テストケースによって長方形の大きさや頂点の密度が大きく異なるので、評価値はタプルで持ちました。前の要素の値が大きいほど評価が高いです。
- （4頂点の次数の和, 追加する頂点の重み)
- （-長方形の外周の長さ, 4頂点の次数の和）
次数の和：1つの頂点が複数の長方形に含まれてほしいお気持ちです
外周の長さ：外周が長いと長方形を追加する際の邪魔になるので短くしたいお気持ちです
頂点の重み：場合によっては次数とか外周を捨ててスコアを稼いでほしいお気持ちです
焼きなましパート
以下の4つの近傍を作成しました。いずれも連鎖的に削除された結果、状態が大きく変化してしまう場合があります。大きな近傍はacceptされにくいので、削除された長方形の割合と同じ確率でその削除を拒否し、貪欲を走らせずに状態を復元するようにしました。
- ランダムに長方形を削除。追加する頂点の重みと残り時間に比例した確率で長方形を削除
- ランダムな直線を1本引いて、外側にある長方形をすべて削除
- ランダムな点を選び、距離が一定値以下の範囲に含まれる長方形を削除
- 最終的に出力する答えから、インデックスがランダムな範囲にある長方形を削除します。
その他・感想
ビームサーチやバックトラッキングするDFSも試しましたが、スコアは伸びなかったです*3。焼きなましで長方形を削除しすぎていてほぼ貪欲になっていることに中盤まで気が付かなかったりしたりするなど*4、スコアが上がってもプログラムが想像通りの挙動になっているかを確認してギャップを埋めていくのは大事だと思いました。あと、AHCではテストケースを無限に生成すればハイパーパラメータに過剰適合することを簡単に避けられるので、Optunaなどを使ってきちんとチューニングすることも大事でした。他の70M台の方たちが何をしてるのか全く想像がついていないので、感想戦を楽しみにしています。
*1:実装では、削除前の長方形を前から順番に追加しながら、削除する長方形と作成不可能な長方形をスキップしました。この時、辺の重なりとかは気にしなくてよく、頂点が存在するかだけ調べればよいです。
*2:他にも「各方向に探索した時に最初に見つかる頂点」をメモ化したり、直線ごとに頂点の座標をheapqueuで管理したりしましたが、却って遅くなりました。恐らく、殆どの長方形はサイズが1x1などと小さいので線形探索が想像より高速なのかと思います。
*3:原因は同じ状態に到達するまでの経路が多すぎるためだと考察しています。試しにタブーリストを持ちながらバックトラッキングすると、若干（pretest換算で1.5M程度）はよくなりました。
*4:これに気づいて諸々の失敗した実験をやり直すと54M→65Mくらいまで上がりました
