AtCoder Heuristic Contest 001に参加しました。
問題はAtCoder Ad。
制約に従うように広告(矩形)を配置して、満足度を最大化する問題です。
結果は提出1505人、得点を得た人1369人のうち、暫定テストでは90位でした。
システスはかなり落ちてしまい118位。
考察
問題
敷き詰め問題（矩形パッキング問題）っぽいけど、一部設定が特殊。
・指定の座標を含む指定サイズにすること
・面積は指定されるが、厳密に守る必要はなく縦横比も自由であること
件数
広告の満足度を取るためには、点としては(y,x),(y,x+1)(y+1,x)(y+1,x*1)の4点を確保しないといけない。そのため完全に隣り合っている広告を両立させることは出来ない。広さ10000x10000*1に対して広告件数は50≦N≦200で、隣り合うことは理論上はあるが非常に稀。*2
形状
実は凄く細長いのが正解のケースがあるかも。干渉しやすさとか、サイズの調整しやすさとか、色々違いそう。
大きさ
小さい広告の方が狭い領域で多くの満足度を生む。衝突時は大きい広告のスペースを削る方が良い。スポンサー料金とは…？
スコア
言い換えをすると、広告毎に[過不足な領域の割合^2]の減点。割合は1以下なので二乗と言っても減少で、特に僅かな過不足であればスコアはほぼ減少しない。領域10%不足でスコア1%減。皆をちょっとずつ不幸にした方が総合的には得。極論、全広告を90%サイズにして完全に敷ければ暫定スコア49,500,000,000が可能。こういう得点ルールなので、基本的には全ての広告を希望位置に置く。
順位表
823,090点以降に同点がほぼいない。万人が使っている貪欲的なものはなさそう？
解法
矩形パッキングで調べると色々出てくる。
ぱっと頭に浮かぶ分割統治法はスライス構造というもので、シンプルながら最高効率とは言えなさそう。シーケンスペアは効率が良さそうだけど、1週間で勉強しないといけないのは辛そうで、計算コストもある程度理解しないと見積もりできなさそう。
あとは最初の2x2(1x1…？)を拡張する方法もあるけど調べて出てくるものでもなかったので、*3スライス構造による分割統治法を使うことに決めました。*4
これは事後感想ですが、その場の分割は上手く行っても後でやっぱり大きいロスを出さないと分割できないというパターンが多く、低速に細かい位置調整をするよりも高速に分割順をガチャガチャ回す方が効果がありそうな気がしました。
最終的にやったこと
初期解の作成
初手のみ縦横それぞれ9999箇所チェック、以降は分割後の2つの領域を大きい1つの広告とみなして[分割後のSize] , [Rの合計] で満足度計算したもの*5*6の合計が最大になる場所で分割するよう貪欲する。9999*2のうち一番良いものを初期解として採用する。
一応書いておくと、広告が0件になる分割や、2x2(1x1…？)を分断するような分割は行わない。
山登り法
0.9を基準値として、評価が悪いノードの先祖(分割元)をランダムに1つ選んで、子孫を全て再構築する。[葉ノードの評価の合計]が改善されたら再構築したものを実際に適用する。0.9未満が無くなったり4000msが経過したら基準を引き上げる。
変形操作としては、階層ごとに以下のものを使った。
・貪欲(50%、もしくは広告数が2)
・[広告間の最善位置]上位20件からランダム(48%)
・全位置の上位50件からランダム(2%)
最終調整
まずは各ノードを基点に貪欲法で再チェックし、山登り法で緩慢になっている部分を引き締めた。その後[大きすぎる領域を縮小]し、[空きスペースを使った拡大]、[隣接広告を動かして拡大]、[隣接広告からスペースを奪う拡大]、という順番で行った後、50msほど[空きスペースを使った拡大]、[隣接広告を動かして拡大]を繰り返した。
特殊対応
広告が絶対にぶつかって両立できない場合、一方を最初から無かったことにして、最後に余ったスペースに詰め込んだ。基本的に97%くらいの点数は安定するので、テストケース1件を落とすデメリットはあまりに大きい。*7
技術的な小ネタ
座標によるソート
広告を希望位置XYそれぞれでソートしたものを作成しておく。
隣り合う広告が分かると分割処理がしやすくなる。
区間ごとの理論値
隣り合う広告を左右に分割する場合を考える。この場合、左端で分割したとき右側の疑似満足度が最も高くなり、右端で分割したときに左側の疑似満足度が最も高くなる。つまりこの2つの疑似満足度を足したものが区間内の理論値となり、理論値でも選別に漏れる場合は区間そのものの計算を足切りすることができる。区間を理論値が高い順に取り出せるよう、優先度付きキューに入れて処理した。
区間ごとの最善値
面積オーバーの満足度を1.0とすると、隣り合う広告間の満足度は弧を反対向きに2つ足し合わせたような山型になる。*8なので三分探索や黄金分割探索が可能。ただし満足度が2つの領域とも1.0になる丘（？）は発生するので、その扱いは要考慮。
全分割位置の最善を求める
区間ごとの最善値を求め、その中の最善値を求めると、愚直に全探索するより速い。
やってみたけどダメだったこと
黄金分割探索
高速化したもののスコアは落ちた。黄金分割が駄目だったというより、スペースが余って最善分割位置が複数ある場合の選び方が良くなかった気がする。
目標サイズを縮小
90%サイズを敷き詰めて99%点取れるなら最初から縮めておけばいいのでは？という浅慮。スコアは上がったか下がったか分からないような変動。言うまでもなく余る10%のスペースを上手く消費するのが肝で、上と同じ原因と思われる。
スコア最善のとき、最善範囲の真ん中で分割する
両方に余裕があればいいだろう、という話でもないらしい。真ん中というのが座標的な中央だったので、それぞれのサイズを考慮して余り率が同じになるようにとかすればまた違ったのかもしれない。
スコア最善のとき、最善内ランダム位置で分割する変形操作
これが駄目ならどうしろと。ただ試したのが中盤だったので、終盤また試しても良かったかも。
反省点
類似問題を調査したのは良いが、全く同じ条件ではないのだから(手法が見つかる＝実績がある＝それを使えばいい)というわけではない。*9
領域の拡大を入れてしまうとスコアがばらつき山登りの改善を目視しにくいので、遅めに実装することにした。中盤は山登りのアルゴリズム改善ばかりしていた。特に他の領域に干渉する拡大の実装は残り1,2時間でギリギリ完成だった。時間があれば縮小拡大の側をもう少し弄って何かできたかも。（縦横比を変えるとか、スライド移動させるとか）
今回はビジュアライザがテスターとしてのバッチ処理に使えなかったのもあり、もうちょっとデバッグ用の情報の吐き出し方を工夫してそこで作業を縛られないようにしたい。ついでにデバッグ並列実行もしたい。
上下左右にそれぞれ同じようなチェックをするのを上手くエコに書けなくてコード量がとんでもないことになった。
テスターを書くのをサボったので、暫定テストケース50件では同じプログラムで何回提出してもWAが出ないのにシステス1000件では6件落ちるみたいなのが起きた。
他の人の解法を見て
AtCoder Heuristic Contest 001 AtCoder Ad - びったんびったん
暫定テスト1位の人
得点率98%(49G点)超えになると、伸縮したりする焼き鈍しを使っている人が多いように見えました。分割統治法は、スライス構造では四畳半的な配置が出来なかったのに加え、階層構造になることで上位階層の再考コストが高くなるのが難点だったように思います。後者については上位階層の再考が少なくなるよう調整できればまた違ったかも？初期解をビームサーチしたり、多点スタートして上位階層の再考を禁止したり。
あとは局所最適解に陥りやすいというのは共通認識のようで、それなら焼き鈍し（改悪を認める）を試すべきだったなーと思いました。†本物†の焼き鈍し、使ったことないんですよね…。
とりあえずはこんなところ。
分割統治法の人だけのまとめとかあれば見てみたいですね（他力本願）
感想
マラソンは、楽しい！
