estie プログラミングコンテスト2022（AtCoder Heuristic Contest 014）に参加しました。
僅差ながら1位をとれました！
コンテストページ
解法
焼きなまし法です。
ランダムに四角を1個削除～それに依存する四角も全部削除したあと、貪欲に四角を作れるだけ作る、というのを繰り返します。
貪欲に四角を作る
貪欲に四角を作る時の評価値はいくつかあって、確率でどれか選びます。
- 完全ランダム
- 追加する点の重みと四角の辺の長さ
- 追加する点の重みに乱数をかけたもの
- 固定パターン配置通りになってるか
この固定パターンのように置くと四角をみっちり置ける。このパターンは方向性があって、前後方向へは四角を延ばしていきやすい。これを上下左右すべての方向へ伸ばしやすいように、盤面上の左右方向と上下方向でパターンの向きを変える。
この固定パターン配置通りになってるかの評価では、パターン四角の4頂点がすでに打たれていれば完成ボーナス、4辺のうち1つでも辺が作られていれば作成不能ペナルティ、そうでないときは打たれている頂点数が多いほど加点というような感じで点数を付けました。
2段階焼きなまし
焼きなまし部分は2段階にしました。
前半の焼きなましでは四角を置ける範囲を初期マーカーの打たれる範囲内に限定しました。限定することで合法手や作成済みの四角が少なくて済むため、高速に探索ができます。
制限範囲の境界部分では特定のパターンになっていると、範囲外の四角の配置がほぼ確定するため、スコアも予測することができます。焼きなましの評価値はこの予測したスコアで行います。
より正しくは以下の図のような条件です。
「緑点の位置にマーカーがあり、赤線部分には辺が無いこと」
ということで、前半の焼きなましでは「四角を置ける範囲を制限」「延ばせる条件を満たさなくなるような辺を描くの禁止」「制限範囲外は延ばした後のスコアを予測」ということをやりました。
（あとは、固定パターンの四角形位置がずれたパターンを8種用意して、焼きなまし多点スタートもやってました）
後半の焼きなましは特に制限なく、実際のスコアで評価します。
うまくいくとこんな感じ
seed=5 初期状態
前半焼きなまし終了時点
後半の焼きなましも終了
ハイパーパラメータ調整
テストケースのMの値が小さいと固定パターン配置がほとんどできなくなります。Mが72未満の場合は固定パターン配置の貪欲をやらないようにし、焼きなましも1段階にしました。
seed=62（M=63のケース）
↓こんな感じで全然固定パターンができない
また、Mにより評価値等を大きく変える必要があると考え、パラメータはMの線形関数になるようにして調整しました。
例えば、前半焼きなましの開始温度はM=31の時は19,341、M=311の時は9,658になりました。（間のMは線形補間で決める）
Mが72未満で処理を分けていること、焼きなましが前半後半に分かれていること、Mの線形関数にしていることでパラメータ数が増えて最終的に74個のパラメータになりました。（Optunaを使って調整しました）
高速化
合法手の計算がボトルネックだったので差分で計算するようにしました。
- 四角を1個描いた場合の合法手更新
- 四角形を複数削除した場合の合法手更新
前者はまだよかったのですが、後者はバグりまくって地獄でした……
ビジュアライザ
軸に平行な四角と斜めの四角で色を変えたり、四角を少し小さめに描いて四角同士が重ならないようにしたのは見やすくてよかった。
依存している四角形の数に応じて色の濃さを変えるのもやったけどあんまり意味なかったかも。
感想
疎なケースではランダムにやるしかないのでは？というところからあまり考察が進まず、雑な評価値とパラメータ調整しかしていなかったので心配でしたが、wleiteさんの作ってくださった集計（https://tc-wleite.github.io/ahc014.html）を見ると疎なケースもそれほど悪くないので、そもそも評価値作るのが難しい問題だったのかな。
密なケースではNが大きい時は1番をとれてますがNが小さいと下がっています。ほとんどN=61のケースしか検討に使ってなかったからかも。これは反省。
あとbit演算を駆使すれば合法手の計算がもっと高速にできたらしい。んぎぎぎ。
問題はすごくシンプルでわかりやすいのに2週間フルに取り組めたのすごい。毎度面白い問題ありがとうございます。
