AHC001 参加記
問題
結果
70 位でした。1ケースだけ TLE していたらしく、少し順位下がった。
やったこと
自明解
各広告が絶対覆う必要のある $(x_i, y_i), (x_i+1,y_i+1)$ に長方形を置くことで、必ず制約を満たす解を得られる。
自明解の改善①
コスト関数が改善する場合に自明解から上下左右に 1px ずつ拡大すると、自明解より大きくコスト改善しそう。 そこで、
- 自明解を初期状態にする
- ランダムに長方形を選択し、伸ばす方向も上下左右 1 方向をランダムに選択
- 2で定めた方向に 1px 伸ばせて、コスト関数が改善し、制約を満たしていれば採用
- 改善ができる間は 2 に戻る
- don't look bit みたいなので、近傍ひと通り見て改善しなかったら探索候補から捨てていくみたいなのをやった
- 時間いっぱいまで 1. からやり直す
をやった。点数は 458,... 程度。
Submission #20681357 - AtCoder Heuristic Contest 001
自明解の改善②
自明解の改善①で、どう見ても伝播して押せるケースがあるのがわかったので、BFS で辿って押せるか判定する処理を追加した。 点数は 478,… 程度。
考察
ここまでで得られた画像を見てみると、より煩雑な操作で改善はしそうだったけど、トップと明確な差があったので中断して考察。
- アルゴリズム選択
- 1px ずつ伸び縮みさせるより、置ける範囲で最大の長方形を置く方法を考えたい
- 制約遵守を保証し続けると動き辛いので、最初は制約違反しても OK にしたい
- 広告どうしが重なるのは OK そう
- 他の広告が含まれるべき点 $(x_i + 0.5, y_i + 0.5)$ を含むのはダメそう
- 局所解を脱出する方法は作りたい
ついて考えた。
アルゴリズム選択
ビームサーチは、ビジュアライザとにらめっこしたり、特徴量を並べても何をどういう順に置けば良さそうかがよくわからなかった。 例えば、
- (要求された広告面積 / 原理上置ける最大広告面積) が大きい順
- 広告面積が大きい順 / 小さい順
- 端から順に置く
みたいなのを考えていたけど、軽く実装して確かめた感じだと上手く行きそうになかった。
また、焼きなますのも考えてみたけど、改悪を許したとしても、十分小さい近傍では次のいい状態につながる想像が全くできなかった。 という訳で、最終的に山登り＋大きめに状態を変えるような操作を時間いっぱい繰り返すことを考えた。
最大の長方形を置き直す
本当はちゃんと説明しようとしたけど、時間が経ちすぎて気力がないので省略。大まかに言うと、
- 座標圧縮
- 塗り絵みたいなことをやって、最大長方形の頂点候補を抜き出す
- その長方形に含まれるべき点からみて第一象限〜第四象限に分類
- 4重ループで全部列挙(多すぎたら適度に省略)
- 経験的には大きくならないけど、一個 TLE したのはこれが原因っぽい？
制約違反をしても OK な方法
2 広告間の面積の重なりを合計したものをペナルティとして入れ、時間と共に線形でペナルティを重くするよう設計した。 これにより、自明解②の push 操作は、重い上に自然に達成されると判断して削除した。
ペナルティを別に入れることも考えたが、共通部分で重なる箇所は面積を直接減らすことでスコアを削減すれば良さそうとわかったため、 重なりが判定された長方形は、その分スコア計算時の面積を両方で減らす方針にした。 が、実装してみたけど全く上手く行く兆しが見えずにやめた。
局所解を脱出する方法
得られた画像を見ると、一部の長方形をまるっきり別の場所に置かないとどうにもならない、というパターンがあった。 そこで、
- スコアが悪い下位5個の広告 A と、それに隣接する広告 B をランダムに選択
- 広告 A, B を 1x1 に縮める
- A をスコア最大の長方形で置き直す
- B をスコア最大の長方形で置き直す
のようにして、kick 相当の処理を入れた。これが相対的にはいい工夫で、最終的には 493... 程度まで伸びた。 小さいケースだと、大体 8,000 回位は kick が行われていたらしい。
やり残したこと
スコアがサチっているけど、変形した方がいい長方形の扱いに少し困った。が、前述の置き直すコストが少し大きめだったので結局なんにもできなかった。
所感
- バグらせはしなかったけど、最大長方形を置き直す部分の処理で無限に時間を溶かした。アルゴリズム力大事すぎる
- 結局、計算量の観点でかなり損をしていたらしい
- TLE を1ケース産んだのは反省ポイント高い
- 実はローカル 1,000 ケースだと1度も起きてなかったので、対処は少し考える必要あり
- 参加人数が多くて賑わってる1週間マラソン(実質2週間)かなり楽しい
- TL を眺めていて、最後までずっと飽きなかった
- フルで毎回参加できるかわからないけど、これからののんびり楽しみたい
- できる範囲でやったことはブログに残していきたい
- とある MM で自分が時間をかけてやった方針をなんも覚えていなかったのが、割とショックだったので
