はじめに

atcoder.jp

開催期間：2022-09-17(土) 15:00 ~ 2022-10-01(土) 19:00 の2週間

AHCのコツ（メモ）
- 評価関数から考察する（スコアを伸ばすにはどうすればいいか？）
- ビジュアライザを色々試して考察する
- まずは初期解を提出する
- 制約から考察する

方針1：短い辺の四角形を優先的に作る

評価関数を眺めて、重心から遠い点を作るか、点をとにかくたくさん作ると良さそうだと予想した。

ビジュアライザをポチポチしてて思ったこととして、重心から遠い点を作ろうとして辺の長い四角形を先に作ってしまうと、その辺が邪魔して作れる点の数が減ってしまうことに気づいた。

なので、まずは辺の長さ1の四角形を作るようにして、徐々に辺の長さを伸ばすようにすればたくさんの点を作れそうなので、そうすることにした。

そのような方針で、とにかく小さい四角形を作りまくるナイーブな実装をした（たくさんバグらせて大変だった）。

提出コード：https://atcoder.jp/contests/ahc014/submissions/35003739

スコア：32,575,448

方針2：乱択 & 試行回数を増やす

山登り法を実装したいと思ったのだけど、どう実装したものか悩む。

出力は、新しく印の付いた点を作る履歴を出力している。この履歴の適当な区間 [start, end] をより良いスコアに差し替える山登り法（個人的に履歴差し替え法と呼んでいる）をしたいと思ったのだが、差し替えるために削除する印のついた点が、[start, end] の区間以外で利用されていると削除するわけにはいかないので、削除してはいけない点を保持しないといけない。なかなか面倒くさそうだし、削除してはいけない点は多そうなので、差し替えが成功するパターンはあんまりなさそうで、スコアが良くなるような気があまりしなかった。なので、別の方法がないかなあなどと考える。

手慰みの新方針として、方針1の実装で、小さい四角形を探索する方向を2パターン作ってより良いスコアのほうを採用することをすると、スコアが1000000程度伸びた。

なので、結構適当に乱択してもスコアが伸びるのではないかと予想した。どの程度伸びるか知りたかったので、そのような実装をした。

実装概要
- 作れる四角形の辺の長さは1にする。
- 始点となる印の付いた点はランダムに決める
- 始点となる点を決めたら、新しく点を作るためにどの方向を走査するかはランダムに決める
  - 新しく点を作れたら、新しく作った点を始点に再度探索をする。
  - この方法を3回ほど試して、スコアの上がり幅が大きいものを採用する
- 新しい点を作れなくなくなったら、辺の長さを増やす。
- 辺の長さがNかつ、新しい点を作れなくなったら終了。制限時間ギリギリになっても終了。
- 制限時間に余裕があるなら、上記を制限時間いっぱい繰り返す。