estie プログラミングコンテスト2022 (AHC014) に参加したので記録しておく。
結果
後半をランダムに作り直す方針で取り組み、システムテストで1,836,678,087点、101位だった。
焼きなまししてない勢としてはまあまあの出来だと思う。前回よりちょっと良かった。
やったこと
まず完全にランダムに生成するソルバーを実装してみた。
時間いっぱいまで作り直すようにしたら27.7M点。制限時間が3秒になっていたので5秒にしたら35.0M。
意外と良さそうな点数だったので、部分的に作り直すようにしてみた。
ランダムで作り、スコアがよかったものを30個取り、それらの先頭の30点だけ残して、残りをランダムで作り直すようにしてみた。37.8M点。
焼きなましの温度管理のように、残す部分をlog(経過時間)にしてみたらだいぶスコアが伸びて43.0M点。
後半あまり良くならないので、全体で2回(つまり2.5秒ずつ)やって良いほうを採用するようにしたら44M点を超えた。
細かい改善で最終的に45.4M点。
密になったら良いのかなと思って近いのを優先させてみたりしたがうまくいかなかった。
ツールなど
- テストケースを10000件生成し、MとNごとにディレクトリにわけた。(Mは25刻み) 分布を確認できるのと、似た条件で10ケースくらい実行するときに便利。
- 2種類の実行ファイルで数ケース実行して結果を試すスクリプトも用意した。
- NとMの平均も取ってみた。N = 45、K=114
工夫・実装内容など
- 縦横と斜め、4方向それぞれで各点をC++のsetに入れて、隣の点と、その距離を取得できるようにした。
- setは遅いので、近い点を総当たりで探すようにするのも書いてみた。近い距離ならこちらのほうが速かった。
- 伸ばせる可能性のある点を集めて、シャッフルして1点ずつ確認するのだが、4方向で伸ばせなくなったらフラグを立てて伸ばせる候補から外すようにした。
- ビームサーチっぽく履歴を持って作り直すようにしたが、NとMごとにパラメータを調整した。
取り組み方について
- メモを残し忘れた。
- やはり実装に時間を使いすぎている感。
- 他の方の解説のように、領域ごとに作り直せばよかった。