待ちに待った AtCoder Heuristic Contest 001 (AHC001) が開催されたので、1週間を犠牲にして参加してきました。結果は暫定14位（495.7億点/50ケース）→システス15位（9912.7億点/1000ケース）。自分には出来過ぎな結果でとても嬉しく思います。パフォ（β版）は2610の橙パフォで、アルゴの最高パフォーマンスである2400を一瞬にして抜き去ってしまいました。

f:id:terry_u16:20210317213545p:plain — 入力例1

この記事とは別に初心者向け解説も書いているのでそちらも是非。

問題概要
考えたこと
方針
- a. 拡大・縮小・平行移動
- b. 破壊
やってうまくいったこと
やってうまくいかなかったこと
やらなかった・やれなかったこと
おわりに

問題概要

正方形のスペースに広告をいい感じに敷き詰めてください。

atcoder.jp

考えたこと

手順とか関係ないので焼きなましっぽい。
長方形がギチギチに詰まってくるので単純な焼きなましだと局所解にハマりそう。破壊とか入れるといいかも。やったことないけど。
全部面積90%でもスコア99%が得られるのでまんべんなく面積を大きくした方がよさそう。
ギチギチになりがちなこと、面積90%でもペナルティは小さいことから、焼きなまし中の途中解はある程度目標面積を小さくしてゆとりを持たせ、だんだん大きくしていくとよさそう。
$1\times10000$ の広告スペース与えられた人かわいそう。本当に顧客満足度高いんですかこれ？

局所解についてなのですが、この問題のスコア分布はおそらく下図のようになっています。

f:id:terry_u16:20210318011726p:plain

図のAの状態になっているとき、本来なら長方形0を縮めて（状態B）長方形2を伸ばす（状態C）と良いのですが、AからBへは焼きなましとはいえよっぽど運が良くないと遷移しません。そのため、2つを破壊して作り直す方針の方が強そうな気がしました。状態Aからダイレクトに状態Cに向かわせるイメージですね。

方針

ランダムな長方形を拡大・縮小・平行移動させる、割とよくある焼きなまし
2つの隣り合う長方形をランダムに選んで破壊して、領域を縦か横のどちらかに2分割し、その境界を黄金分割探索*1で決め打ちしながらヒストグラム上の最大長方形問題を解く焼きなまし

を用意して、

$1\times1$ の広告を要求地点に $n$ 個置く。
初期解生成のためa.を回す。ゆとりを持たせるため、目標面積は $0.7$ 倍する。*2
メインの焼きなましとしてb.を回す。時刻 $t (0 \le t \le 1)$ での目標面積は $0.7^{1-t}$ 倍として、だんだんと $1$ 倍に近付けていく。
3.を乱数のseedを変えて何回か試し、一番良かった結果を保存する。
仕上げとしてa.をもう一度回して全てをごまかす。

をしました。動画にするとこんな感じです。

AHC本当にお疲れ様でした。49,577,244,111点で暫定14位。

(1)ランダムな長方形を拡大・縮小・平行移動させる焼きなまし
(2)2つの隣り合う長方形をランダムに選んで破壊し、境界を嘘黄金分割探索で探しながら最大長方形問題を解く焼きなまし
を用意して、(1)→(2)→(1)の順で流しました。 #AHC001 pic.twitter.com/GIQsNxmiuR
— TERRY (@terry_u16) 2021年3月14日

焼きなまし中にぷるぷるしているところと、3.になった途端にいきなりハチャメチャになるところがお気に入りです。

atcoder.jp

a. 拡大・縮小・平行移動

これは初心者向け解説に書きました。今回はこれを採用している人を多く観測したように思います。解説記事から変更したところは目標面積を上記の通り変更したことと、変化量を $1$ 固定ではなく $[1, 50^{(1-t)} ]$ からランダムで選ぶようにしたくらいです。式の根拠は適当。

ところで、これ動画で見るとするとかなり焼きなまし（金属工学）っぽくないですか？b.で内部結晶に不均一性が生じている金属組織を一旦高温に持っていくことで各長方形（金属原子に相当）の運動を活発にさせ、そこから徐冷することでエネルギー的に安定な状態へと落ち着かせていくのがめちゃくちゃ原義の焼きなましっぽくて大興奮してしまいました（機械工学の話になると突然饒舌になるオタク）。

b. 破壊

ここがメインパートです。局所解脱出のためどうにか破壊を入れたくて考えました。

まず適当に長方形 $i, j (i \ne j)$ を選びます。このとき、入力で与えられた $(x_i+0.5, y_i+0.5),$ $(x_j+0.5, y_j+0.5)$ を含む最小の長方形を作ってみて、その長方形と他の $n-2$ 個の長方形が干渉しなければ、長方形 $i,j$ が「隣接している」と判断します。この判定は愚直 $O(n)$ ですが、隣接していない場合は割とすぐ干渉する長方形が見付かることが多いです。その場合は $i, j$ を選び直します。

f:id:terry_u16:20210317231049p:plain:w300

隣接している場合は、一旦2つの長方形を破壊した上で縦か横に領域を切り分けます。この領域の境界を黄金分割探索で決め打ちして、それぞれの領域で最大の長方形を作ったときのスコアを最大化することを考えます。

ちなみに三分探索や黄金分割探索は、凸でない一般の関数に対しては最大値どころか極値すら求められないケースがある *3ことが知られています。今回もおそらく嘘解法なのですが、どうせ極値が求められないケースは稀だろう*4ということと、最後に焼きなましで全てを誤魔化す予定であることから気にしないことにします。また同様の理由で、厳密解を求めず $r-l\le16$ くらいになったらさっさとreturnすることで定数倍高速化を図りました。*5

f:id:terry_u16:20210317231125p:plain:w300

ここで予め座標圧縮をしておくと、ヒストグラム上の最大長方形問題に帰着できます。ABC189のC問題ですね。これは普通にやると $O(n^2)$ ですが、蟻本のp.298を読むとstackを上手く使うことで $O(n)$ になると書いてあるので、やります。このとき、 $(x_i+0.5, y_i+0.5)$ を必ず含むように注意します。

f:id:terry_u16:20210317231138p:plain:w300

境界が決まったら長方形を置きます。長方形の大きさが必要以上に大きくなってしまった場合は左右どちらかに適当に寄せることにします。

座圧は普通にやると $O(n \log n)$ ですが、setで座標を管理しながら上手いこと差分だけ追加・削除をすると毎ループ $O(n)$ に落ちます。黄金分割探索の回数は $d=|y_i-y_j|$ として $O(\log d)$ で、最大長方形問題は1回あたり $O(n)$ なので、合わせて $O(n\log d)$ でこの問題を解くことができました。*6 *7

f:id:terry_u16:20210317232833p:plain:w300

ここまでが1つの変形操作です。良ければ採用、悪ければ確率的に採用します。a.だけだと局所解からなかなか脱出できずスコアが伸び悩んだのですが、開始2日目にb.を入れると一気にスコアが伸びました。*8おかげでその後の時間が長く取れたので、解法ガチャに成功した感があります。

やってうまくいったこと

焼きなまし温度の高温化

これはめちゃくちゃ効きました（490.0億→493.5億、手元1024ケースでも+0.7%）。直感的に上げすぎだろって思うくらいに上げたのですが、局所解にハマりやすい問題はこのくらいの高温から徐冷してあげた方が良いのかもしれません。

さ……さささささ3位！？！？？？！？！？ pic.twitter.com/8mV9Yl6LIW
— TERRY (@terry_u16) 2021年3月7日

可変要求面積

改善量としては+0.1%ないくらいですが、これも結構効きました。

Vecを固定長配列化

Vec<T>（C++でいうvector<T>）はヒープメモリ確保が入るので、スタックメモリを使う固定長配列（とスライス）に片っ端から書き換えたら実行速度がざっくり1.7倍になりました。正直ここまで効くとは……。ただし残念ながらスコアは0.02%しか伸びていません。

多点スタート化

局所解に陥りやすいためか、3.の焼きなましを乱数seedを変えていくつか試し、一番良い結果を4.に流すと点数が伸びました。今回の問題では $n$ が可変なので、 $n$ ごとに試行数を適当に変化させています。

座標圧縮パートの高速化

差分の追加・削除に $O(\log n)$ 、圧縮後の配列生成はsetを舐めることで $O(n)$ となり、全体で $O(n)$ で座標圧縮ができます。最終日に思い付いたので入れたら座圧速度がざっくり2倍になり、手元ケースでスコアが0.02%伸びました。最終日ともなるとだいたいやり尽くしていて、たった0.01%上げるのもめちゃくちゃしんどいのでまあ……うん……。

ビジュアライザの動画化

自作ビジュアライザを作っている方もいたのですがそんな技術はなかったので、

実行中一定時間間隔で状態を保存
全てファイルに書き出し（1000個くらい）
全部公式ビジュアライザに食わせてsvgを作る
適当なフリーソフトでpngに変換
AviUtl*9でパラパラ漫画化

をしました。動画化は初めてだったのですが、これのおかげでかなり考察が捗りました。問題は重い腰を上げて動画化したのが最終日の昼だったということなのですが……。

提出してモチベ上げ

順位表の点数を信用するなというのは初心者向け解説記事に書いた通りなのですが、それはそれとして30回くらい提出してしまっていました。理由は、順位が上がると嬉しいからです。

手元で1024ケースを回して、有意にスコアが伸びたときだけ提出していました。ジャッジサーバに負荷を掛けてしまってすみません。解説記事書いたので許してください。

手元テストケースの並列実行化

なんだかんだで手元で1024ケース×300回くらい試行錯誤しているので、同時32ケース並列実行の恩恵がかなり大きかったです。Ryzen 3950Xありがとう……。

やってうまくいかなかったこと

やってはみたもののうまくいかなかったことの方が多いです……。マラソンは根性。

重なった状態を許容

重なった状態にペナルティを付けつつ許容し、時間経過とともにペナルティを増やしたりもしましたが、処理が重いせいかスコアが落ちてしましました。これで上手くいった方もいるようですが、今回の解法だとb.で局所解脱出が図れていたのであまり効果が出なかったのかもしれません。あと雑にやると下図のような状況になって身動きが取れず破滅しました……。

f:id:terry_u16:20210318013456p:plain:w300

スコアが低いやつを作り直し

スコアが低い長方形を重み付き確率で消して焼きなましし直すみたいなのを作ったのですが、微妙でした。今になって考えると、その周りもまとめて消さないと破壊前と似たような長方形ばかり出来てしまいそうですね。

拡大するとき他の長方形を押しのける

入れてみたんですが、微妙でした。拡大・縮小近傍を使ってぷるぷる焼きなましていれば、わざわざ押しのけ処理を入れなくても勝手にエネルギー的に安定した状態（スコア関数の極大点）になりそうな気はします。

黄金分割探索の代わりに境界を乱択

$\log$ が付くのが嫌だったので乱択も試しましたが、若干スコアが落ちました。最大長方形問題が重めの $O(n)$ で試行回数が稼げないので、この場合はちょっと時間を掛けてでも良い解が得られる確率を上げた方が良いのかもしれません。

長方形がどこに属するかbit管理

広告スペースを $5\times 5$ くらいに分割して、どこに所属しているかbit管理することで定数倍高速化できないかと思いましたが、微妙でした。

焼きなましをまとめる

手順3.と5.をまとめて焼いたらスコアが落ちました。大きな変形と小さな変形は相性が良くないのかもしれません。

やらなかった・やれなかったこと

近傍の多様化

2個を破壊して作り直すだけだと近傍が少ないので他にも何か考えようとしましたが、何も思い付きませんでした……。近くの $k$ 個をまとめて破壊して育て直すみたいなのは次回以降取り入れていきたいです。

乱数を指数分布にする

焼きなましのときの変化量を指数分布にするのは思い付きませんでした。基本小さい値が選ばれつつたまに大きく変化してよさそう。

MM124

もともと被らなかったはずが1週間延期されてもろ被りになって笑いました。

さすがに生活が破滅するのでパス……。両方参加された方は本当に凄いと思います。

有休取得

年度末の引き継ぎでバタバタしており、涙……。

おわりに

最終的に1500人くらいの方が提出されていたようで、大変めでたく思います！今後マラソン界隈がどんどん活発になってくれると嬉しいです。自分も負けないように頑張ります。

*1:後述しますが、これはおそらく嘘解法です。

*2:単純に入力で与えられた要求面積を0.7倍し、それを用いてスコア計算をしています。

*3:noshi91さんがHackケースを作成して下さりました。

*4:上記の問題では嘘解法にも関わらずシステスまで通ってしまいました……。

*5:何でもかんでもミリミリ詰めずに費用対効果を考えるのはなんだか仕事っぽいですね。ｳｯ……。

*6:嘘解法なので、解けていません……。

*7:オーダー上は座標圧縮分が消えてしまいましたが、実際はそこそこ重いです。

*8:さすがに最初から全部入りではなく、b.のコア部分の実装だけです。

*9:名前だけしか知りませんでした……。

TERRYのブログ

最近は競技プログラミングにお熱。

AtCoder Heuristic Contest 001 (AHC001) 参加記