AHC001に参加した

AtCoder 初の Rated ヒューリスティックコンテストである、「AtCoder Heuristic Contest 001」に参加しました。

問題概要

リンク

$10000 \times 10000$のスペースの中に$n$個の広告を貼りたい。以下のような$n$個の広告スペースの要望が与えられるので、なるべく全広告の満足度の平均が高くなるように広告を配置せよ。

広告の要望と満足度

各広告の要望は、$(x_i,y_i,r_i)$で表される。

• $x_i,y_i$は必ず広告に含ませたい座標を表す。この点が広告内に入っていない($(x_i+0.5,y_i+0.5)$が広告に含まれない)場合、その要望に対する満足度は 0。
• $r_i$は広告の希望面積である。面積が$r_i$に近いほど満足度が高い。具体的には、面積を$s_i$として満足度$p_i$は以下の式で計算される。

$p_i = 1-(1 - \frac{{\rm min}(r_i,s_i)}{{\rm max}(r_i,s_i)})^2$

• 全ての$i,j$に対し、$(x_i,y_i) \neq (x_j,y_j)$が成り立つ。

広告の形

広告は矩形で表現される。各広告の要望に対し、矩形の左上座標と右下座標を出力する。ただし、広告が重なっている場合は失格となる。

スコア

全広告の満足度の平均がスコアとなる。

自分の解法

暫定テストで、486 億点、147/1505 でした。

貪欲法

この問題は、各広告を$(x_i,y_i,r_i)$を囲む 1 マスとすれば最低限の解になります。この状態から上下左右にどれだけ伸ばすかをうまく調整していきたいです。

まず、矩形の上下左右を伸ばす方針として「他の広告では利用できない方向に先に伸ばした方が良さそうだ」という考えに至りました。

そこで、以下のような貪欲法を考えました。

• 点$(x_i,y_i)$が$10000 \times 10000$の広告スペースの上下左右の辺に近い順に並べる。

• ↑ で決めた順で各広告の上下左右を伸ばす。

  • 広告スペースの辺との距離が近い順で上、下、左、右を並び替え、その順で 4 方向伸ばす。
  • 伸ばす長さは、${\rm min}$ (伸ばせる長さ, 面積$r_i$を満たす長さ)

この方法は$O(n^2)$です。これだけで、450 億くらいの点数になりました。

解の探索

次に、「広告の順番」「伸ばす方向」をあくまでパラメータとし、上記の解法で決めた「広告の順番」「伸ばす方向」を初期解としてよりよいパラメータの探索をすることを考えました。広告の順番のパターンは$n!$、伸ばす方向のパターンは$(4!)^n$です。

適当に「広告の順番」「伸ばす方向」に対して局所探索を行ってみたところ、「広告の順番」は数回の改善で局所最適解となるのに対し、「伸ばす方向」は$n=200$の問題では 2 分たってようやく局所最適解に到達するレベルだったので、順番は一度局所最適解を見つけたらその順で固定してしまい、「伸ばす方向」の局所探索に時間を使う方針にしました。

これで 485 億に到達しました。

貪欲法の高速化

最大で伸ばせる長さの判定

上述の貪欲法は、$n$個の広告について上下左右に伸ばせる長さを$O(n)$で調べるため、$O(n^2)$です。 元々、上下左右全てについて全ての広告との衝突を調べていましたが、左にどれだけ伸ばせるか調べる際に、自身よりも右に中心がある矩形を調べる必要がないことに気付き、前処理として$(x_i,y_i)$が自身より上、下、左、右にある矩形を記録してその情報を使うようにしました。 この高速化で、試行回数が 1.6 倍くらいに増えました。

前の解の活用

解$X$から、1 つの広告の伸ばす方向に変化があった解$X'$に遷移するとします。 上述の貪欲法では、「広告の順番」が、伸ばす方向に変化があった広告よりも前であれば何も影響を受けないので、解$X'$に対して貪欲法を適用した時、伸ばす方向に変化があった広告よりも前の広告は$X$と全く同じ状態になります。このことを利用し、前の解とその差分で計算できるようにしました。 これにより、試行回数が 3 倍くらいに増えました。

一連の高速化で、485 億 => 486 億に上がりました。

その他の工夫

最善解に対する解の改善

探索終了後の最善解に対して、以下のような解の改善を試みました。

• 各広告を、可能なかぎり左に平行移動させる。
• 満足度が最大でない各広告を左に伸ばす。
• 上下右に対しても上記手順と同じことをする。

これで必ずわずかにスコアが伸びました。

多スタート局所探索

高速化により$n$が小さい問題では局所最適解に余裕で到達するようになってきたので、多スタート局所探索を行うようにしました。これで 50 ケース試した時の最低スコアがマシになりました。

検証環境

アルゴリズムとは直接関係ありませんが、アルゴリズムが改善したことの検証は、50 ケースの平均スコアを計算するシェルで行っていました。

迷走

$s_i$の素因数分解

最初、満足度が 1 になるためには矩形の縦横が共に$s_i$の約数である必要があるという考えで、縦横を s_i の約数で縛るという方針でやっていました。既に難しい問題がさらに難しくなり破綻しました。

感想

まあまあの精度の貪欲法により、ある程度のスコアの解に高速で到達できたのはよかったです。 しかし、局所探索対象のステートの評価に高コストな貪欲法を使ったために局所最適解にすら到達せず、一般的なヒューリスティック解法の枠組みがそれほど適用できなかったのが無念です。

また、この解法の弱点として、表現力が弱く、ある程度良い解にしか到達しないというのがありました。 おそらく、例え大域最適な「伸ばす方向」の組を得られたとしても 490 億には到達しなかったと思います。 ビジュアライザで見ても問題ごとにスコアのムラがあり、この解法だと絶望的なスコアしか出ない問題例も恣意的に作り出せるのではと思います。

よってこの貪欲解法は初期解生成などの使用にとどめ、それ以降は近傍の評価が低コストな別の方法を適用することを考えていれば、と思っています。

良いスコアの解 1

良いスコアの解 2

悪いスコアの解 1

悪いスコアの解 2