マラソン初心者の橙コーダーが一週間本気で AHC に挑戦した話
TL; DR
コンテスト後システス前の段階で 34th / 1370 でした。
https://gyazo.com/501ee2809db59e91fd34021115e76935
(システス後)少し下がった。
https://gyazo.com/06bda1ac2f86a8ceefe6f2f146180170
方針概要
以下の図のように、グリッドに仕切りを入れ、二分割することを再帰的に繰り返す。
https://gyazo.com/d065b2bb00454dfd522d5be3b59b316d
再帰の終端にあたる各長方形内では、その長方形に含まれる広告を以下のように(左から/右から/上から/下から)貪欲に詰め込んでみて、一番上手くいったやり方を採用する。
https://gyazo.com/415844411e470ae8e665ceb656929957
ここで、グリッドの分割を表現する二分木を焼きなますことを考える。まず根だけからなる木(仕切りを全く持たない分割)から始めて、仕切りの追加(葉の追加)、仕切りの削除(部分木の削除)、仕切りの移動の三種類の近傍を設定し、焼きなましていく。
焼きなましが終わったら仕上げとして、ランダムに広告を選び、そのサイズを微調節してスコアが上がるなら変更する、ということを適当な回数繰り返す。
ここまでを実装してスコアは 49.2 G くらいだった。焼きなましの温度を調節したら 49.4 G まで上がった。そこから高速化や近傍の選択などを工夫してみたが、劇的にはスコアは上がらなかった(かなり評価関数が多峰っぽいので、最初のうちは並列に焼きなましを走らせて、途中から一番いいのに集中する、という形をとったら、0.05 G ほどスコアが上がった)。
得られる解は、だいたい以下のようになる。
https://gyazo.com/b7eba9aa8d38389a89e385134e52e723
https://gyazo.com/20fcb10c5fb58eb212a782bb613bca9c
https://gyazo.com/12737a00a51dbe50edf1b0fbac4043d0
改善案
焼きなましの時間を伸ばしてもスコアが 49.5 G 弱までしか上がらなかったので、そもそも二分割していくやり方では表現力の限界があるような気がした。たとえば以下のように、4 つの広告が噛み合って長方形に収まっているような配置は、上手く表すことができない。
https://gyazo.com/3ef834a5a41bc2125e7905910d556112
このあたりをケアできるように枠組みを改善したら、もう少しスコアが上がるかもと思った。
知見
コードの微調節を始めてからスコアが上がらなくなった。上を狙うためには、常に根本的な改善を狙っていかないと駄目だと思った。
コードの性能をプロファイラで分析してみたら、予想外に時間を使う処理が多かった。たとえば、スコア計算関数で何気なく使っていた std::swap 関数が、なぜか処理時間の 10 %を占めていた(スワップベタ書きに直したら治った)。
使えそうと閃いたアイデアは数百個はあったが、実際に改善に繋がったのは 10 ~ 20 個程度だった。何事もやってみないと分からないなと思った。
焼きなましの温度調節はかなり重要と分かった。悪い温度といい温度で 0.4 G くらいスコアが変わる気がする。チューニングには optuna でも使ってみようかなと思ったがよく分からなかったので平方分割状にグリッドサーチした。三時間くらいかかった。今度から optuna を使おうと思います。
生産性がかなり対数という感じで、長時間打ち込んでも最初の数時間以上の成果が出ない日も多かった。これは固有スキルかも。
視覚化技術の不足を感じた。たとえば焼きなまし中のスコアや分割の二分木をプロットして振る舞いを分析するなどできそうだが、やり方が分からなかった。自力でビジュアライザを書ける技術が必要と思った。
最初ハズレ方針(グリッドを縦だけに分割し、仕切りの位置を焼きなまし)を引いていて、スコア 48.3 G くらいで止まっていた。限界を感じ思い切って二分木型の方針に変えたらスコアが 1G 上がったので、変えてよかった。
途中まで(49.4 G まで)テストのやり方が雑で、1 ケースだけ実行して雰囲気で方針のよさを測っていた。手元で 50 ケースバッチ処理するコードを書いてから、コード変更の影響が分かりやすくなった。真っ先にテスト環境を整えることが重要。
最終的に、どのコードをシステムテスト用に提出するか? にけっこう意思決定が必要と感じた。プレテストのスコアがよくても、プレテストのケースに過学習していたりジャッジの調子に左右されていたりというのがあるので、有望そうなものいくつかを、手元で十分な数のサンプルを使ってチェックする必要があると思った。
終わりに
このあと 9 時からの ARC 114 のテスターをしたのでぜひ出てください。