参加しながら考えたこと試したことの源泉かけ流し。
最終的な方針は まとめ にまとめてあります。
問題概要
https://atcoder.jp/contests/ahc001/tasks/ahc001_a
N 個の長方形型の広告を 10000 × 10000 のフィールドに敷き詰める。各広告には 必ず長方形内部に含めないといけない座標 と 目標の面積 が設定されている。各広告は他の広告と被ることは許されない。できるだけ各広告の面積が目標に近付くよう広告を敷き詰めよ。
1 日目
とりあえず問題を読んで、どシンプルな valid な解、すなわち各広告がリクエストされた点を含む面積 1 の正方形となるような解を書いてビジュアライザを眺めてみる。
考えたこと
- スコア関数的に、例えば各長方形について平均 50% の達成率とするなら、100 点と 0 点を半々よりも全広告について 50 点の方が良い。
- 満点付近は詰めても伸びが悪いので、面積ぴったりを狙う必要は薄い。
- 小さい広告ほど融通が効きやすそうなのでデカい広告から先に決めていくべき？
- 最終的には辺を押し引きする焼きなまし？
- それ以外の遷移の候補は？
- 満を持しての AHC で焼きなましやるだけってことはないんじゃあないか？
- 焼きなまし以外のアイデア
- 周辺に広告の中心点がないようなエリアをうまく有効活用したい。
- 端から詰めていく？
- 近くにある複数個の広告についてその面積の合計に近いエリアをざっくりブロックとして確保して、その中で部分問題を解く。
- 過去のマラソンでも強い人達が部分問題に分割して解いてるのを何度も見てきた。
- k=sqrt(n) くらいの値で k-means？
- 全体をブロックに分割する際も同じロジックでいける…かと思いきや、含まないといけない点が複数個になるという違いはある。
- しかも、それらの点がすべて端っこに固まるみたいなのは避けたい。
- うまく分割しないとどう足掻いても低スコアになるブロックが発生し得るので、考えることは多そう。
- 部分問題は解きやすい反面ブロックを跨ぐような長方形を選べないことになり自由度は下がるので、どうなんだろう。
- 暫定テストの満点は 50,000,000,000 点。
- 上位は 3 時間弱で 96% くらいのスコアを出してる。結構しっかり埋められるんだな。
- これ終盤かなり細かい部分の戦いになるのでは？
- どシンプル valid 解の seed 0~199 スコア平均 * 50 は 1,289,556、順位表眺めた感じ横並びゾーンは 823,090。そんなに差出る？
- 広告の目標面積が 2 桁以下くらい極端に小さくなるケースはどれくらい発生するだろうか。
- 小さい広告は絶対的には小さい誤差がスコアに響き得るので、もしかしたら特別なケアが必要かもしれない。
- svg は seed の値をファイル名にしてどっかに溜めて、vis.html 内で指定した seed のを動的に見れるようにすると便利そう。
- AtCoder の Standings は絶対スコアなので 1 回提出してローカルのテスト結果とのスコア比みたいなものを確認した後は頻繁に提出する意味は薄そう。
ひとまず考えるのはこの辺にして、山登りを書いてその結果を眺めつつまた考察をしようかな。
とりあえず、初期状態は面積 1 の正方形からスタート。ランダムに選んだ長方形の上下左右の辺を幅 1 だけ動かして（他の長方形と衝突するならそれを押し縮めて）みてスコアが改善するなら採用する山登りを書いてみた。手元で 200 ケース走らせた平均点 × 50 の値（順位表と比較するため。以下、スコアの表記はこの値。）は 47,859,219,317。
この図を見て気付いたけど、いくつかのどデカイ広告を犠牲にすれば全体の 96% を埋めなくてもスコア 96% は出るんだよな。
これ見るとブロックに分けて部分問題は筋が悪いように見えるなぁ。
あとひとつ気付いたのは、今広告が衝突したときの辺の押し引きを伸縮方向にしかしてないけど、こういうケースだと伸縮方向と垂直な方向に避けてあげたほうが良い。
vis.html を弄って svg の seed とどのバージョンの解法によるものかをページ上で切り替えられるようにした。
高速化をしたり複数個の乱択山登りをやって一番良かった解を選ぶやつをやって手元で 47,989,559,923。試しに提出してみたところ暫定スコアがほぼ同じくらいの値になったので後は提出しなくても大体のスコア感は掴めそう。
2 日目
とりあえずこの山登りを育てていってみる。
乱択山登りをするときは同スコアの状態の遷移も試してみた方が良い、他のところに効くかもなので。既に目標面積に達した長方形にも変化を付けるため、ランダムに選んだ長方形が目標面積に十分近ければ形はそのままに可能な限り上下左右にスライドするようにしてみた。
スコアは 48,080,409,583。
面積 1 の状態から幅 1 ずつ大きくしていくのは無駄に時間がかかるので、初期状態を工夫したい。
具体的には、広告のリクエストされた座標から見て左上、右上、左下、右下にどれだけ他の広告と衝突せず領域を確保できるかを列挙してから舐めることで、その座標を含みかつ他と衝突しない最大の長方形を割り出し、（それが目標面積を超えていたら縦横比そのままで縮めて）それを採用する。
また、目標面積の小さい広告は後から融通が効くので、目標面積の大きい順で初期状態を決めていくことにする。
スコアは 48,469,980,553。
焼きなましをしたい…が、今の遷移でたまにスコア悪化でも採用をやってみてもあまり効かなかった。うーん。
要は局所解から抜け出せるようにしてあげれば良いので、現状をぶち壊してくれる新たな遷移を追加してみる。
具体的には、選択した広告のサイズを一定確率で思い切って 1 × 1 に縮める。そして再度その広告が選ばれた際には先程の初期状態を選ぶロジックを流用し、面積最大の長方形を探してそれを採用し直す。こうすればその広告が一時的に縮んでる間に他の広告がその領域に侵食してきて、良い感じに現状をぶち壊せそう。
スコアは 48,663,269,688。
2 日目終わりの様子はこんな感じ。
初期状態の決め方を変えたことにより細長い広告が増えた。
3 日目
プロファイラを走らせてみたら広告どうしの衝突判定で全体の 50% くらいの時間を使っていることが分かった。
その衝突判定をよく見ると処理に無駄があったので書き直して、これでそこそこ速くなった。
bool isCollided(const Ad &ad1, const Ad &ad2) {
- bool isCollidedX = !(ad1.maxPt.x <= ad2.minPt.x || ad2.maxPt.x <= ad1.minPt.x);
- bool isCollidedY = !(ad1.maxPt.y <= ad2.minPt.y || ad2.maxPt.y <= ad1.minPt.y);
- return isCollidedX && isCollidedY;
+ if (ad1.maxPt.x <= ad2.minPt.x || ad2.maxPt.x <= ad1.minPt.x) return false;
+ return ad1.maxPt.y > ad2.minPt.y && ad2.maxPt.y > ad1.minPt.y;
}
ついでに今まで山登りは 1,000,000 ステップ繰り返していたのを 500,000 ステップに減らし、倍の数の山登りを試せるようにしてみた。
スコアは 48,801,867,424。
高速化やステップ数の削減で試す山登りの回数を増やすことがスコア増加に繋がることが分かった。他にも何か高速化はできないだろうか。
今は長方形の幅を 1 ずつ増加させているが、これを幅 2 にしたら半分のステップ数で事足りそう。もちろんそれだと幅 1 レベルの細部を詰められなくなるので、最後は幅 1 で見てケアしてあげる。
スコアは 48,847,825,962。
確実にスコア増加には繋がるだろうけど実装を後回しにしていた、伸縮方向と垂直な方向に広告を避けられるなら避ける処理を実装する。
スコアは 48,946,242,570。
隣り合う二つの広告について、位置関係をグルっと 90 度回転させることでスコアを改善できる場合があることに気付いた。
スコアは 48,957,122,664。思ったより伸びないな…。
3 日目の終わりの様子はこんな感じ。少し青さが減った。
4 日目
今は各広告の初期状態を決めるとき目標面積の大きい順で決めていたが、必ずしも面積の大きい広告が置きづらいとは限らない。そこで、前回の山登りの結果を見て、スコアが低かった順で次回の山登りの初期状態を決めていくことにしてみる。
スコアは 49,078,233,493。
壁を動かした結果スコアが悪化した際の遷移の切り戻し処理等にバグがあったので直した。バグがあってもそれっぽく動いてしまうのでマラソンは怖い。
スコアは 49,150,889,219。
複数の山登りを試してベストだった解に対して、スコアを伸ばせる箇所が残っていないか全ての広告に対して山登り中の遷移を試してみるのをやった。
スコアは 49,168,670,539。
辺を伸ばして他の広告と衝突したとき、その衝突した先の広告の他の辺を伸ばして再帰的にぐにぐに動かすのを試してみたんだけど、処理が重い上スコアは伸びなかったので、捨てた。
5 日目
アイデアが尽きたのでパラメータの調整でお茶を濁す。長方形のサイズを一定確率で思い切って 1 × 1 に縮める処理の発生確率を 1% から 0.333% に下げた。
スコアは 49,191,299,735。
隣り合う二つの広告の位置関係をグルっと 90 度回転させる処理にバグが見つかったので直した。
スコアは 49,235,527,874。
6 日目
広告の初期状態を決めるとき、今までは目標面積を確保できるならそれを採用していたが、なんとなく序盤は盤面をゆったりさせた方が良い状態に転がりやすい気がしたので、初期状態では目標面積の 25% までしか確保しないようにしてみた。
スコアは 49,268,547,124。
7 日目
今は現状をぶち壊す遷移として一時的に 1 × 1 に縮めるやつしか試してないが、他にもぶち壊す遷移を試してみたらどうだろう？例えば、シンプルに辺を縮めてみるとか。
中盤までは 75% の確率で幅を 2 増やす、25% の確率で幅を 4 減らす、にしてみたらなんか良い感じにスコアが伸びた。
スコアは 49,341,352,775。
山登りのステップ数等のパラメータを調整した。
スコアは 49,350,565,658。
8 日目
序盤は盤面をゆったりさせた方が良い状態に転がりやすい、を信じるとするならば、序盤は各広告の目標面積を実際の値より小さい偽の値でスコア計算をさせて、ステップを進める中で徐々に目標面積の値を実際の値に近づけていくと良い感じになるのではないだろうか。
最初は目標面積の 70% を偽の目標面積として山登りを開始し、終盤にかけて線形に 100% に変えていってあげると良い感じにスコアが伸びた。
スコアは 49,393,315,871。
提出時の暫定スコアは 49,408,406,799 となり、なんとか 494 億の壁を超えることができました。やり！
しばらく貼ってなかった seed = 1 の様子はこんな感じ。
9 日目
この記事を書いた。
まとめ
暫定順位 / スコア
46 位 / 49,408,406,799
方針
- 乱択山登りをたくさん試して、一番良かった解を返す。
- 山登りの遷移は、ランダムに選んだ広告の辺を伸ばす。
- 他の広告に衝突したら、衝突した先の広告を縮める、もしくは横にズラす。
- 衝突した 2 つの広告の位置関係を 90 度回転させてみたりもする。
- たまにスコア度外視して状態をぶち壊す。
- 広告の辺を縮める。
- 広告のサイズを一時的に 1 × 1 にする。
- 山登り前の初期状態の決め方を工夫する。
- 目標面積の最大 25% 程度の面積を、既に初期状態を決めた他の広告に衝突しないよう確保する。
- 前回の山登りでスコアが悪かった広告から優先して確保する。
- 遷移のスコア差分計算時には、実際の値より小さい偽の目標面積を用いる。
- 山登り終盤に近付くにつれて徐々に真の目標面積に近づけていく。
