https://atcoder.jp/contests/ahc001
N個の長方形を 10000x10000 グリッド上に配置せよ
- 各長方形には必ず含まないといけないセルが1つずつ指定されている
- 重なっちゃいけない
- 指定セルに重複はない
- 各長方形にはちょうどいい大きさ r_i が指定されている
- min(r_i, area) / max(r_i, area) = s_i
- s_i * (2.0 - s_i) の得点
- 1 - (1-s)^2, 2s - s, としても同じ
- つまり r_i ぴったりだと 1 点。 超過したり未満だったりは減点
- \sum r_i = 10000x10000
- 理想的には盤面をちょうど埋め尽くす
- N = [50, 200] だが生成方法的に 小さい方によってるはず (50 * 4^[0,1])
# 50 * 4**[0,1]
count 1000.000000
mean 108.794676
std 42.988915
min 50.014264
25% 71.727937
50% 100.700117
75% 141.364746
max 199.769534
普通に考えたら長方形を伸縮/移動させる焼き鈍し。
2d bin packing problem っぽいけど、こっちはサイズが丁度じゃなくていい分緩和問題っぽい。
下手に bin packing 風に考えるよりサイズの自由度を活かした方がいい？
2つの長方形に関して
- min(x1_i, x1_j) > max(x0_i, x0_j) &&
- min(y1_i, y1_j) > max(y0_i, y0_j)
のとき重なってる
-
交差判定？
- 愚直 (50 <= N <= 200 だから変なことするより軽そう)
- 各長方形と関係しそうなやつは限られるので確認するやつを限定する
適切に限定できていれば invalid な解はそもそもスコア悪いので出現する可能性は低そう
(自分の面積、相手の面積、距離的に損失が大きくなるような関係、他の長方形でガードされるような関係) - 分割統治
bitset でその領域に長方形 i が含まれるか否かを管理
拡張した領域で交差するかどうかを検証
-
焼き鈍し
- (cx,cy) から 4 方向にどれだけ伸ばすか、みたいな値を増減させる
- 余白ボーナス？
- 複数の長方形が接続している場合、まとめてシフトするとか
(全体を左に動かす、みたいなことをすると有効な時に、増減近傍だけだと難しそう) - シフトせずに衝突してるやつを押しやるのもありか
- 伸ばしてる距離をたまにリセットするキック
- 伸ばしてる距離 * k (k<1) 倍するとか
-
分割統治
- 10000x10000 からはじめて、領域を 2 (k) 分割していく方針
- 別れた後の領域で必要な面積 \sum r_i とその領域の大きさが大体同じになるように分割
\sum r_i == 10000x10000 という条件を勘案したもの - ゲーム木探索みたいな感じになるのかな？ ビームサーチ？
- 多分これだけだと細かいところが上手く分割できないだろうから、初期解をこれで作って焼き鈍しがセオリーな気がする
- ノード内の長方形だけで焼き鈍し動かすと良い？
-
遺伝的アルゴリズム…？
- GA が効くのはたっぷり時間があるときだからなぁ
f(L,R) = min(1.0, Area_L / Require_L) + min(1.0, Area_R / Require_R)
面積が大きい分にはあとで融通が利きそう、という気持ち
とりま生スコアで普通に焼き鈍し
push (衝突したやつを押しやる) をやってみたけど微妙？
計算量が若干増える上、あまりacceptされなさそうなんだよなぁ
各広告ごとの面積達成率を見てみると、 0.98-0.99 が並ぶ一方で 0.03 とかがあったりする。
上位がケース平均 0.99 取ってるってことは平均面積は 0.95 を達成していることになる
大きく低いやつがあるとダメっぽいので、点数が低い広告の重みを増やす？
それともいっそのこと逆に点数が低いのを切り捨てる方向？
まぁ次に試すのは分割統治の方だね
sum_i 集合の大きさ^2 - 1
とかをビームサーチのキーにする？
どうせ満点取れないなら必要な面積大きいやつを 0 点にしてどこかにおいやってしまうのはどう？
1-5 個ぐらいならセーフでは？
枝刈り後の次数が大きいやつは多分面積が大きいので思い切って使わないようにしてしまう
もしくは素直に面積大きいやつ。
近いところのを複数不使用にしてもそんなに意味なさそう。 一定の範囲で最大1個みたいなかんじかな
使わないやつもどこかに配置する必要有。
座標圧縮して適当な領域に置けばいい
-> なんか全然ダメ？
むしろ下がった。 現状結構余白があるからあまり意味がないのかも
やっぱり分割統治かなぁ
上の方から段々に広告を加えてくのはどう？
95% の面積達成率 -> 殆どの広告は適切に配置できてるはず
-> 段々に加えてほぼ完ぺき配置にしてから次へ、とすると多すぎて身動き取れない状況になりにくそう
上からと下からを後で合わせる？
とりあえず greedy に split するやつを実装
最後の shrink なしで 0.8 ぐらいのスコア
これを初期解にして SA -> 0.95 安定で悪くはなさそう
-
段々に加える -> 全然ダメ
-
重みを調整 (スコアが悪い広告に大きな重みを加えて広い領域を得やすくする気持ち) -> ほんとに若干しか影響しない気がする
-
思い切って不使用のやつを生やす
-> 全然ダメ -
greedy split + shrink fit
領域の大きさ >= r_i
のやつはほぼ満点が取れる (誤差和が 1e-6 とか) これだけで 0.91 - 0.96 ぐらい -
split は大体半分にしてくので O(N log N) で全部分けられる (マージソートの逆)
-
ビームサーチの概算スコアとしてもこの計算量ならアリアリ
結論。
-
SA は最後の調整用
-
ベースは split
split の速度が出なくて？？？
x 昇順の id で持ってるやつ、 ビットで管理すると早い？
コピーコストが支配的になってるわけじゃないなら後回し
ビームサーチの状態のカット方法でもうちょっといいのないかな…？
縦カットと横カットで両方から一定数使うようにとか？
これとあと焼き鈍しの再実装
ビームサーチ
x 昇順に見ていって、 i, i+1 の間でカットする
sum l : sum r = area_l : area_r
x_i, x_{i+1} の間で上の式に近くなるような位置で分割
最適な場所を中心にランダムで複数個所？
ビームサーチの状態
-> カット候補列挙
-> 上位 B 個
-> その後貪欲カットした時のスコアを計算
-> 上位 W 個を採用、次のビームへ
こんな感じ
リファクタリングして永続スタックでビームサーチ
bit -> 遅い
縦カット横カットのそれぞれのベストは絶対に greedy で評価をする対象にする
-> 有効っぽい？
ビームサーチでカットした部分領域内で焼き鈍しを葉から根の方に向かって
-> 微妙。 微改善はするけど大きく焼きなますのと変わらない
ビットマスク + 領域分割で衝突判定高速化
-> 遅くなる。 枝刈りするやつもリスクとパフォーマンスのバランスを考えると使わない方がよさそう
ビームサーチの最適化
-> N=50..200 だから TLE の危険性
本番環境でも試さないといけない
アイデア
窓焼き鈍し
適当な領域を指定して、その中にある広告だけを動かす
少しずつ全体をシフトして―とかが有効な時に有用そう? 結構大きい広告が多いのでサイズ感には注意
でも N がそもそも小さいのであまり意味ないかも
とりあえずテスト書かなきゃ…
壁に寄せるスコア変換なしのキック -> ギチギチ
ビームサーチの k を小さくしたらスコアかなり改善
-> 多様性た大切
とりあえず 100 ケースでテスト実行
平均 0.9861911099999997
つまり * 50 で 49.3 点
seed 71 が 8 秒近くかかっちゃってる
この辺を処理しないといけない
多様性の確保？
size 2 以下の split は次のキューへ入れちゃっていいんじゃない？
ここから終了後
余裕がなくて書いてなかったこと
ビームサーチのカット候補列挙が多すぎると多様性が失われる (ある状態を親にする状態で飽和)
-> i, i+1 間では best のみを拾うようにする (正規分布でサンプリングしてた)
-> 多様性が生まれて目立ってスコア改善した
多様性がスコアに直結するっぽいので、 キューを複数個用意して、状態 S からは キュー q に突っ込むようにする
\sum |block|^2 をキーにするのはある程度効くけど時間調整が難しいから単純にターン数 (カット回数)
スコアの 95 % はビームサーチで決まってるので小さいケースで 1 秒切ってるようなのはもったいない ビーム幅とかを時間と相談して調整するように調整
1 ターンのビームの状態で
\sum (次に分割する領域内の広告の数) * (カットの提案数)
が時間に直結してるっぽいので、これの閾値を設定。
ビームキューの頭からカット候補列挙していって、途中でこの値を超えた後のビームの状態は破棄
スコアには好影響？誤差？
時間に応じてこの値を線形に下げていくことで 2-3 秒ビームサーチに使うように設計できた
1000 ケースでこけないか確認。 提出。 お疲れ様
反省
パラメータ調整で 49.5 は乗せられた気がする。
天皇賞春が勝てない…
焼き鈍しでもうちょい粘ってればよかった…。 次は頑張りたいです。