AHC014では、ナンバリングAHC自己ベストとなる暫定64位となりました。対戦ありがとうございました。やったことを記載します。
システムテストを経た最終結果も64位でした。
なお、筆者はRustで参戦しています。
1日目（9/17土）
問題文を読解。ルールは分かったけど、どうすると格子点が都合良く増やせるか、アルゴリズムが全く分からない。2週間コンテストは、重実装を前提としているはずだが、実装の方向性が分からない。
2〜3日目（9/18日〜9/19月）
焼きなましにするか、ビームサーチにするか検討。手数の上限が決められていない（あえて言えば盤面の大きさ？）ので、ビームサーチの方が実装しやすいか。しかしながら、局所的な最適スコアが、最終的な最適スコアに結びつきにくそうなのと、焼きなましの方が当たれば良い順位が狙えるため、焼きなましでいくと決定。
焼きなましの設計
- データの持ち方: そのままアウトプットになる長方形のリスト（
Vec<Rect>） - 初期解: 貪欲解。着手可能な手の中で、最も局所スコア（新たな格子点の単独スコア）が大きいものを、次々と選択していき、着手可能な手が無くなるまでプレイアウトする。
- 近傍: 任意の1手を、その時着手可能な別の手に変更する。それ以外の手は無変更でリプレイする（変更の影響で無効になった手はスキップする）。最後にまだ着手可能であれば貪欲プレイアウトする。
初期の設計は上記とは若干違っていたが、ほぼ変わらない。逆に言うと、これ以外の良い設計は作れなかった。
この近傍、表現を変えれば「任意の1つの長方形と依存する長方形を削除して、1手ランダムに長方形を選択した後に、貪欲プレイアウトする」というものでした。上位陣の近傍に似ていた・・・。
焼きなましの実装のスケルトンを作り、自明な出力（長方形を1つも作らない）まで実装完了。
提出14,048,321点。376位。
4日目（9/20火）
初期解としての貪欲解を作る。ただし、初期条件によっては1秒以上かかるため、焼きなましを数回しか回せないことになる。性能改善が必要。
提出33,366,040点。129位。
5日目（9/21水）
盤面データの持ち方を工夫して、数10msオーダーで貪欲解が作れるようになる。本格的に焼きなましを実装。
提出46,151,738点。29位。
ランキング2ページ目にジャンプアップ。焼きなまし作戦大成功、だが、ここからたいして伸びなかった。
もう少し伸びた
— toast-uz (@ToastUz) September 21, 2022
RectJoinのseed=0で772836点を獲得!!!https://t.co/Hx1s5hQaHH#AHC014 #estie #visualizer pic.twitter.com/LrDpTTxix4
6〜12日目（9/21水〜9/27火）
良い近傍探しが進捗しないため、性能改善により焼きなまし回数を増やすことにする。計画的に性能改善をするために、パフォーマンスプロファイルを取る。RustだとFlameGraphが良さそうである。MacでのFlameGraph実行は制約があるため、VirtualBoxにubuntuを立ち上げ、その中で実行してみた。
インストールは日本語でいくつか記事があるが、古くていずれも使えなかった。GitHubの本家のドキュメントに従うとインストールできた。
実行時は提出プログラムのバイナリを作成してから、毎回以下を実行すればよい。
$ echo -1 | sudo tee /proc/sys/kernel/perf_event_paranoid
$ cargo flamegraph -- ahc014-a < tools/in/0000.txt > tools/out/0000.txt
出力結果例はこちら。
画面写真では雰囲気しか分からないが、有効手を求める処理にほとんど費やしていることが判明。そこを集中的に修正。順序維持しつつ挿入削除をするデータでもBTreeSetやBTreeMapを使うのではなく、Vecを使って必要時にソートした方が、定数倍が速くなる。
1週間かけた地味なチューニングで、seed=0で焼きなまし約5000回だったのが、3倍程度に高速化された。途中何度も、ドラゴンクエスト10オフラインに逃避。
提出50,484,360点。念願の50M超えを果たす。
50Mクラブに入りました😎
— toast-uz (@ToastUz) September 26, 2022
#AHC014 pic.twitter.com/e6LSYixQE6
13〜14日目（9/28水〜9/29木）
もはや有効な打ち手無く、パラメータチューニングで誤魔化す。焼きなましがかなり不安定であり、時々ハイスコアからかなり下に落ちていってしまう場合あり。1000回程度ハイスコア更新が無い場合に、再度ハイスコア時点からやり直すように修正すると、若干安定してスコア改善した。
提出51,734,843点。この時点で42位くらい。
15〜16日目（9/30金〜10/1土）
あっという間に60位台に降下。。。最後はoptunaにがんばってもらって、グラフを見つつ良さそうなパラメータでえいやっ 、と投げる。なお、今回のように乱数でスコアが安定しない問題の場合、optuna-dashboardのグラフを見て（赤い曲線は筆者が脳内で描いたもの）、全体傾向の中で最適そうな値を選択すると良い。逆に、「2000ケース1回」とかで判断すると、バリアンスが判断できないので間違うと思う。結果論かもしれないが、グラフで見切った最適値とシステムテストの平均得点とが、かなり近接していた。
seed=0は人工的な特殊条件なので、seed=0を外した200ケースを回しました。
後から考えると、ケース選択もoptunaの試行のたびに乱数で実施したほうが、良いかもしれません。
最終ハイスコア51,965,249点。暫定64位でフィニッシュ。しかしながら最終提出スコアは50,974,779点だったりする（泣）。システムテスト後の最終順位も64位であるが、スコアを暫定換算すると、約51.5M点だったので、パラメータチューニングには失敗していないと思われる。
#AHC014 乱数ガチャで結果不安定でした。
— toast-uz (@ToastUz) October 2, 2022
パラメータチューニングは、2000ケース単独1回で見極めるよりは、少量ケースを多くoptunaで試行して、optuna-dashboardでバリアンスまで見えるようにして判断したほうが、よいと思いました。 pic.twitter.com/z4jnQg9iI4
終わりに
結果としては、焼きなまし作戦が当たり、早期に良い順位につけるものの、経験不足のためそこからの打ち手が思いつかず伸び悩み、となりました。それでも、ナンバリングAHC自己ベストになったので、よかったです。