AHC014の日記

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ページ目にジャンプアップ。焼きなまし作戦大成功、だが、ここからたいして伸びなかった。


<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">もう少し伸びた<br><br>RectJoinのseed=0で772836点を獲得!!!<a href="https://t.co/Hx1s5hQaHH">https://t.co/Hx1s5hQaHH</a><a href="https://twitter.com/hashtag/AHC014?src=hash&amp;ref_src=twsrc%5Etfw">#AHC014</a> <a href="https://twitter.com/hashtag/estie?src=hash&amp;ref_src=twsrc%5Etfw">#estie</a> <a href="https://twitter.com/hashtag/visualizer?src=hash&amp;ref_src=twsrc%5Etfw">#visualizer</a> <a href="https://t.co/LrDpTTxix4">pic.twitter.com/LrDpTTxix4</a></p>&mdash; toast-uz (@ToastUz) <a href="https://twitter.com/ToastUz/status/1572562047501762563?ref_src=twsrc%5Etfw">September 21, 2022</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

# 6〜12日目（9/21水〜9/27火） 

良い近傍探しが進捗しないため、性能改善により焼きなまし回数を増やすことにする。計画的に性能改善をするために、パフォーマンスプロファイルを取る。RustだとFlameGraphが良さそうである。MacでのFlameGraph実行は制約があるため、VirtualBoxにubuntuを立ち上げ、その中で実行してみた。

インストールは日本語でいくつか記事があるが、古くていずれも使えなかった。[GitHubの本家のドキュメント](https://github.com/flamegraph-rs/flamegraph)に従うとインストールできた。

実行時は提出プログラムのバイナリを作成してから、毎回以下を実行すればよい。

```bash
$ echo -1 | sudo tee /proc/sys/kernel/perf_event_paranoid
$ cargo flamegraph -- ahc014-a < tools/in/0000.txt > tools/out/0000.txt
```

出力結果例はこちら。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156600/8e603ffa-a45b-381d-a61e-f6e7dafa92a0.png)

画面写真では雰囲気しか分からないが、有効手を求める処理にほとんど費やしていることが判明。そこを集中的に修正。順序維持しつつ挿入削除をするデータでも`BTreeSet`や`BTreeMap`を使うのではなく、`Vec`を使って必要時にソートした方が、定数倍が速くなる。

1週間かけた地味なチューニングで、seed=0で焼きなまし約5000回だったのが、3倍程度に高速化された。途中何度も、ドラゴンクエスト10オフラインに逃避。

提出50,484,360点。念願の50M超えを果たす。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">50Mクラブに入りました😎<br> <a href="https://twitter.com/hashtag/AHC014?src=hash&amp;ref_src=twsrc%5Etfw">#AHC014</a> <a href="https://t.co/e6LSYixQE6">pic.twitter.com/e6LSYixQE6</a></p>&mdash; toast-uz (@ToastUz) <a href="https://twitter.com/ToastUz/status/1574390161928224769?ref_src=twsrc%5Etfw">September 26, 2022</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

# 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点だったので、パラメータチューニングには失敗していないと思われる。

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr"><a <blockquote class="twitter-tweet"><p lang="ja" dir="ltr"><a href="https://twitter.com/hashtag/AHC014?src=hash&amp;ref_src=twsrc%5Etfw">#AHC014</a> 乱数ガチャで結果不安定でした。<br>パラメータチューニングは、2000ケース単独1回で見極めるよりは、少量ケースを多くoptunaで試行して、optuna-dashboardでバリアンスまで見えるようにして判断したほうが、よいと思いました。 <a href="https://t.co/z4jnQg9iI4">pic.twitter.com/z4jnQg9iI4</a></p>&mdash; toast-uz (@ToastUz) <a href="https://twitter.com/ToastUz/status/1576371255082913793?ref_src=twsrc%5Etfw">October 2, 2022</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script>

# 終わりに

結果としては、焼きなまし作戦が当たり、早期に良い順位につけるものの、経験不足のためそこからの打ち手が思いつかず伸び悩み、となりました。それでも、ナンバリングAHC自己ベストになったので、よかったです。