AtCoder Heuristic Contest 001 AtCoder Ad - びったんびったん

AtCoder Heuristic Contest 001 - AtCoder

Heuristic Contest の初開催おめでとうございます。楽しませていただきました。

seed: 1 f:id:hakomof:20210314202005p:plain

方針

greedy に初期解を求め、少し山登り法をします
実行時間の前半、 1. を繰り返しそのうちの最良解を後半の初期解とします（多スタート）
後半、「キック近傍+少しの山登り」を近傍とした山登り（これは少しではない）をします

山登り法

広告の位置サイズを変更して良くなっていたら遷移する、ができるので焼きなまし法系だなあと思います。

近傍 1: 広告 1 つを最適化

要素を 1 つ 2 つ変えるというのは頻出なのでします。

広告を 1 つ選び、それ以外すべての広告の位置サイズを不変としたときの（ありうる矩形すべてのうちの）最適な位置サイズに選んだ 1 つの広告を変えます。これが平均 O(N) でできますが少し難しい。

なぜランダムな位置サイズではなく最適な位置サイズにしたかというと、最適な矩形に包含されるような良くなさげな矩形をランダムは多量に含むので、有効な近傍の割合がとても減ると思ったからです。

平均 O(N) にする

ありうる矩形のうち他の矩形に包含されない矩形を列挙し（矩形列挙）、
列挙した矩形それぞれに、その矩形内での最適サイズを求めて最良をとれば（矩形内最適化）、

最適な位置サイズが求まります。

矩形列挙

最小の広告を左右にできるだけ伸ばす
上下にできるだけ伸ばす
矩形として列挙
さらに上に伸ばすために左右を最小限に縮め、 2. にメモ化再帰。下に伸ばすのも同様

これは O(N³) ですが、実際には上下左右を他の広告に囲まれているため平均 O(N) になります。

矩形内最適化

int 最適な幅[広告のid][高さ] をテーブルで持ちます。 1 から矩形 H までの h それぞれに、矩形 W < 最適な幅[id][h] なら愚直に、でなければテーブルを引けば O(H) で求まります。

このテーブルを disjoint sparse table 化すると区間 min or max を O(1) で求められるので、最適な幅が矩形 W 以下であるような高さから矩形 H までの区間最良をとれば O(1) で求まります。

あわせて平均 O(N) にできました。

近傍 2: 広告 2 つを最適化

要素を 1 つ 2 つ変えるというのは頻出なのでします。

近くにある広告 2 つを選び最小にし、近傍 1 を順番に適用します。

遠くにある広告はお互い干渉しないのでそれぞれ独立に近傍 1 を適用するのと変わらず、いたずらに遅くするだけなので完全に無駄です。それぞれの広告でマンハッタン距離が近い順に 5 コを近い広告としました。この 5 という数は明らかに近傍 2 を適用したいであろう広告のペア群として少ない（漏れうる）ですが調整の結果ですね。その外側の山登りのイテレーション数とのバランスです。

また、近傍 1 を順番に適用するというのはこの 2 広告間に限定しても最適ではありません（例えば 2 広告間の分断線を 3 分探索すれば最適になりそう）。これは速度とのバランスと後述する膨張近傍でカバーできるからで、近くにある広告だけなのも同じです。しかし、近傍 1 では最適な位置サイズを求めていて、こんな風にこの部分はは遅くても正確に、あの部分は高速だが不正確に、というバランス配分が求められるのはヒューリスティックコンテストのおもしろいところだと思っています。

膨張近傍

ここで問題のスコアリングを思い出してみると、満足度 1.0 と 0.8 の 2 広告より、 0.9 と 0.9 の 2 広告のほうがスコアが良いです。そして、近傍 2 は片方をめいいっぱい良く配置してもう片方をあまったスペースにできるだけ良く配置するという主旨なので問題のスコアリングと相性が悪いです。なので、広告の満足度を均等に上げるために、

スコアが良くなる限り上下左右辺を 1px ずつ大きくすることにしました（他の広告と接しているならそれらを縮めてなおスコアが良くなる限り）。