AtCoder Heuristic Contest 001 参加記

 

ついにレーティングがつくマラソンコンテストがAtCoderで開催されました。嬉しいね

マラソンコンテストにがっつり参加するのは2020/11のこどげオババコンぶりで2回目になります。

 

問題概要

問題ページ

$ 10000 \times 10000 $ のスペースと $N$ 個の広告に関する座標 $(x_i+0.5, y_i+0.5)$、面積 $r_i$ が与えられる。各広告は与えられた座標を内包するような長方形であり、広告どうしが重なってはいけない。$s_i$ を $i$ 番目の広告の面積として、以下の式により定められたスコアを最大化するような広告の配置を決定せよ。

\[ score = \sum_{i=1}^{N} \left( 1 - \left( 1 - \min(r_i,s_i)/\max(r_i,s_i) \right)^2 \right) \]

 

結果

 

最終的な順位は50位でした！！！！（順位賞が欲しい）

最後の2日間で4909から4938まで上げられたのがデカ過ぎました

 

※2021/03/18 追記

コンテスト終了後のシステムテスト後の順位は49位でした！
パフォーマンスは2268でマラソンのレーティングは1268になりました
マラソン水色と申します

 

方針

　全体の流れとしては、山登り法を主軸に置いて、ヒューリスティックな操作を考えては追加、考えては追加・・・と繰り返していました。当初は焼き鈍し法で取り組もうと考えていたんですが、温度設定がよく分からずスコアが微妙になってしまっていたので途中で山登りをすることにしました 🗻。

 

以下に最終提出で使った操作を書いていきます。

 

- 土台の部分

まず、$10000\times 10000 $ のスペースを全部持っておくわけにはいかないので、どうすれば効率よく広告どうしの隣接判定や、広告の伸縮ができるかを考えます。自分の実装では、x1, x2, y1, y2毎にunordered_setを10001個ずつ用意して管理することにしました。これにより、広告の大きさを変えた際の座標の追加・削除や隣接判定が容易に行えました。広告の伸縮に関しては、幅を±1したいときは隣接面を参照して、可能な限り伸ばしたい場合は+1ずつ伸ばすのではなく、他の広告との衝突判定をして決定します（中盤まで+1ずつ伸ばしてたけどこっちの方がずっと速かった）。

 

- expand

各広告の面積を可能な限り広げます。

別の広告と隣接していない場合は+1して、隣接している場合は他の広告を押すことによって+1だけ広げられるかチェックしました。

queueで順に広告を見て、改善されたならまたqueueに突っ込むことを繰り返すため、まんべんなく広告の面積が広がってくれます。

 

- corrade

ある広告の幅を-1して、その広告と隣り合った広告を+1して改善されるかチェックします。

この操作が多分MVPで、スコアにかなり貢献してくれてました。これもqueueで更新フラグを立てて操作を繰り返します。小さく押し込まれていた広告は大体これで解決されているはずです。

 

- reset_one

 ある広告を $1\times 1$ にリセットして、4方向に対する24通りの全探索で可能な限り伸ばすことを繰り返した後、元から最も改善されたものを採用します。

正直なところあまりスコアに寄与しなさそうだと思っていたんですが、この操作が選ばれる確率を小さくするとスコアが目に見えて下がっていたので、最後まで使っていました。

 

- reset_neighbor

 ある広告と隣接する全ての広告を $1 \times 1$ にリセットした後、最初の広告から優先的にreset_oneを行います。

スコアの小さい広告ほど選ばれる確率が高くなるようにしています。ガチガチに固められて動けなくなっている状況を打開するのが目的です。reset_oneが終わった後は更なる改善の余地があるはずなので、expandとcorradeも適用した後の全体スコアが改善されたかチェックしました。

 

- penetrate

 ある広告を$1 \times 1$にリセットした後、選んだ方向に進んで突き当たった広告を手当たり次第に$1\times 1$にリセットしていきます（破壊神）。

これもスコアの小さい広告ほど選ばれる確率が高いようにしています。

reset_neighborでは網羅できないような複数個先の広告まで固められている状況を打開するのが目的です。面積を十分大きくできるまで破壊を終えたら終了します。

 

- change_side

ある広告と隣接している別の広告をランダムに選択して$1 \times 1$にリセットした後、隣接面と異なる方向に優先的に広げます。例えば上下に隣接している2広告は 横の面で隣接しているはずなので、リセット後に縦向き→横向きの順に幅を広げていきます。

局所解にはまっている広告間の関係を変えるのが目的です。

これ全探索していたのでかなり重くて、1/100 で選んでたけど2000msとか3000msとかかかってました。全体のスコアにはある程度貢献してました。

 

- adjust_1

全操作の最後に広告の幅を±1だけ調整します。各広告について$x, y$の一方を+1、もう一方を-1することを改善されなくなるまで繰り返します。

これは最大長方形問題を解くのが理想で、頑張れば1広告あたり $O(N)$ で解けるはずなんですが、サボりました。かなり後悔してます

 

- adjust_by_stretch

スコアが小さい広告から、強制的に各方向に幅を+1してcorradeを適用することを繰り返します。

$r_i$ と $s_i$ の差が大きい広告絶対許さないマンとして機能してくれることを期待しました。

これは最終日に考えたもので、そこそこの確率でこの操作を選択するようにしたらかなりスコアが伸びてくれました。最高

 

 

 

おわりに

この9日間ずっと楽しんで取り組むことができました。設定はシンプルだけどマリアナ海溝より奥が深い問題で非常に面白かったです。

ヒューリスティックな操作をたくさん並べただけの山登り法でも高順位を達成できたのは嬉しいですね。他の方々とは違って手数で殴るような方針を取っているので、こんな戦略でもそれなりの点を取れるんだなと参考になれば幸いです。

上位勢の感想をパーッと見た感じだと、焼き鈍し+α の方針が多かったので、もう少し焼き鈍しを考えてあげるべきだったかもしれないです。面積を $r_i$ より多少小さく見積もってもスコアの損失が少ない性質ももう少し活かすべきだったと思います。

改善点をいくつか残したままコンテスト終了を迎えてしまうのはかなり勿体ない気がするので、次回はアイデアを試しまくりたいね

 

AHC002も出るぞ出るぞ