AHC001 参加記
AtCoder Heuristic Contest 001に参加した！技育祭でchokudaiさんが「ヒューリスティックスコンは自分の書いたプログラムを育てるのが楽しい」のようなことを言っていたけれど、かなり実感した。
一週間のうち、最初の3日と最終日にがっつり取り組んだ。ICPC模擬地区があったり、技育祭が三日間あったりで取り組んでない時間のが長かった。
システス前46,877,146,209点で431位。
やったこと
Introduction to Heuristics Contestの解説がRustだったので、Rustで自分も取り組んだ。vis.rsからscoreやintersectをそのまま持ってこれたりして楽だった。
一日目
- 1*1の正方形を作る 823090点
- 外周までの距離で各長方形をソートしてから、各長方形を他の長方形と交差しないように拡大 453億点
二日目
- 局所探索法を書く 目標面積より小さい長方形（公式ビジュアライザにおいてより青いものから）を拡大する 交差したらほかの長方形を縮小 456億点
三日目
- 焼きなまし法を書く 456億点
- 適当に長方形を選んで縮小する近傍を増やす
最終日
- 縮小する近傍を減らす
- バグがあったので直す 468億点
自分の提出↓
https://atcoder.jp/contests/ahc001/submissions?f.User=ntk_ta01atcoder.jp
あとは、グラフを書いたり
（焼きなまし法実装直後は解が全然動いてなくて困惑した）
（終盤はちゃんと動くようにグラフを見ながら温度いじってた）
GitHub（private）にコードとメモ上げたりしてた。最終日に改めて取り組むときに何やってたっけ？を思い出せてよかった。けれどやっぱりまだ使い方がちゃんとわかってない。
コンテスト終了直後、TLに大量に知見が流れていたのでまとめていきたい↓。
自分用人々の知見まとめ
hakomoさん
#AHC001 https://t.co/LpG29J0EgM
— hakomo (@hakomof) 2021年3月14日
多スタートと山登り。なんか近傍で賢いことしてそう。
TERRYさん
※後日参加記を書くとのこと
AHC本当にお疲れ様でした。49,577,244,111点で暫定14位。
— TERRY (@terry_u16) 2021年3月14日
(1)ランダムな長方形を拡大・縮小・平行移動させる焼きなまし
(2)2つの隣り合う長方形をランダムに選んで破壊し、境界を嘘黄金分割探索で探しながら最大長方形問題を解く焼きなまし
を用意して、(1)→(2)→(1)の順で流しました。 #AHC001 pic.twitter.com/GIQsNxmiuR
長方形を破壊するみたいな発想出なかったな。最大長方形問題ってなに…？ビジュアライザが動くと楽しい（それぞれ途中結果を出力してパラパラ漫画的に作ってるらしい）。
TERRYさんによる初心者向け解説
めちゃくちゃ丁寧で参考になる。Tipsまで全部読むべき。さらに参加記も書くそうで…すごいな…。
takumiさん
※後日参加記を書くとのこと
#AHC001 暫定25位（49.524G）
— takumi152 (@takumi152) 2021年3月14日
やったこと（簡略版）
長方形の上下左右端のいずれか1方向（もしくは2方向）の位置の変化を近傍とした焼きなまし。初期状態は全ての長方形の大きさを10000x10000としたもの。評価関数は面積によるスコア-重なってる部分の面積によるペナルティ（時間経過で増加）とした。
ペナルティをつける、みたいなのやったことない（自分は重なりを許さないような実装をしました）。
じろうさん
僕の解法では
— じろう (@Jiro_tech15) 2021年3月14日
「4方向に引力を発生させる」
「面積の最大値を時間経過につれて50%->100%」
が特に重要でした#AHC001
自分も平行移動みたいなことをしたかったのだけれど、実装できなかった。引力？を発生させるみたいなのすごい。
さはらさん
Dynamic AABB Tree を作って多点開始焼きなまし
— さはら (@shr_pc) 2021年3月14日
近傍は
・膨らませる
・ランダム変動
・接触している箱のペアを「転置」する
で、重なった場合は1段階だけ押し出しを試みる
焼きなまし過程を観察したかったのでコードに埋め込めるタイプのビジュアライザを作りました（svgで描画→html出力） #AHC001 pic.twitter.com/FoT4et83cU
知らないTree出てきた。自分は膨らませる近傍しか最終的に実装できなかったけれど、人々はいろいろな近傍を作っていてすごい。あと今回みたいな局所解にハマりやすい感じ（これ問題の性質ではなく自分の実力のせいだったりしますか？）だと多点スタートがやっぱり強そう。
ymatsux ACさん
#AHC001 496.6億解法
— ymatsux AC (@ymatsux_ac) 2021年3月14日
焼きなまししました。
遷移（１）：
・目標値より大幅に小さい広告をランダムに一つ選んで、それをランダムな方向に拡大する。拡大量は [1, 10000] の範囲から指数分布でサンプルする。拡大するとき他の広告の中心に衝突したら、拡大方向と垂直な方向に縮小し衝突を回避（続）
考えてることとしてはこういうことがやりたかった。空白地帯を使ったり、ランダムな変形をいれるなどができなかったな。
可視化大事だな～～と感じたあたりまとめ
#AHC001 お疲れ様でした．
— si💊 (@iiljj) 2021年3月14日
暫定スコア 486.9 億点，148位でした．
焼き鈍しです．ときどき形を矯正したり破壊したりして，いいスコアになる state を探しました．
typescript でビジュアライザを作って，スコアが悪い問題を観察しながら進めていました．せっかくなので動画を貼ってみます． pic.twitter.com/BxxjMkuJb6
焼きなましは途中状態を眺めるの必須なのでこういうのを作っていた #AHC001 pic.twitter.com/673ZMxYkio
— tomerun (@tomerun) 2021年3月14日
そういえばとりあえず可視化は改善点を見つけるのに便利なので、実行しているリアルタイムにブラウザに通信してソルバにヒント与える仕組みを作っていました。(SocketIOありがとう...コード: https://t.co/97AWfaQNvo) #AHC001 pic.twitter.com/nDS0GHc3bi
— きゅうり (@kyuridenamida) 2021年3月14日
次回はこういうの作りたいな。
iwashiさん
序盤の順位表から考えたことやスコアの伸びた/伸びなかった方法など、かなり細かく一週間何をしていたか書かれていてめちゃくちゃ参考になる。
optさん
#AHC001 お疲れ様でした〜
— opt (@opt_cp) 2021年3月14日
制約付き非凸 (連続) 最適化ソルバを雑に書いて、その出力解を雑に丸めて整数解を得ました。49.1 G点でした。
optさんだけ違う問題を解いているかのよう……。
ウォンバットさん
#AHC001 よく考えると、広告が大きすぎる分には後で削ればいい (連続とみなせることが効いている) ので関係ないことに気づきます。そこで領域全部を広告で埋めるという制約を課しました。すなわち、画像のような途中状態を取りうるということです。 pic.twitter.com/v5Vieu9PU5
— ウォンバット (@packer_jp) 2021年3月14日
こういう方針もあるんだ、という気持ちに。
binさん
49.42Gでした。
— bin💊 (@5bin101) 2021年3月14日
焼きなましで、初期解は823090になるやつ。
遷移は2つあって、
①どこかの辺の長さを1変える
②ある広告を選んで、それとそれに接している広告を初期解に戻して①の山登り#AHC001
縮小や破壊、実装できずにちゃんとわかってなかったのでこういうことなのかやってみよう～～～と思った。
人々の知見が多すぎてまとめきれてない。Twitterの#AHC001 タグももうちょっと漁りたい。
次のAHC002も楽しむぞ～～～
