RECRUIT 日本橋ハーフマラソン 2022夏(AtCoder Heuristic Contest 013) 参加記
概要
RECRUIT 日本橋ハーフマラソン 2022夏(AHC013)の参加記です。
結果は、16位とよかったですが、結構迷走してました。
問題
サーバルームがグリッドで与えられる。
各マスはサーバか空きマスで、サーバはK種類がそれぞれ100台ずつ存在する。
今、サーバの移動を何回か行ったあと、サーバ間を接続する、という操作を行って、できるだけ同種のサーバで大きなクラスタを作りたい。
操作を100K回まで行えるとき、クラスタで決まるスコアを最大化せよ。
2 <= K <= 5
NはKによって範囲が決まる(疎〜密)
最終的に提出したアプローチ
#AHC013 #rcl_procon 暫定16位351k。
— phyllo(フィロ) (@phyllo) 2022年8月16日
丁寧に近傍(つなぐ/切る、つなぎ着替える、1手動かす、クラスタ切る)を書いた焼きなましをして、最後に不純物除去と遠くのを持ってくる処理をgreedyに実施。
K個ぐらいの山があるから、行き来できる巨大近傍を探してたけど結局見つけられず、、、 pic.twitter.com/4wc3CdFIii
- 盤面を状態に持つ焼きなまし＋不純物除去＆遠くのサーバを持ってくるルールベースの処理
- 評価関数は、スコア関数そのまま。差分更新。
- 近傍は、以下を適当にKごとに割合を変えて遷移
- 焼きなましの結果で、小さなクラスタができていた場合、それらの接続を解除して、ルールベースで、不純物除去＆遠くのサーバを持ってくることで改善
- あと細かい高速化で若干イテレーション回数を増やした
時系列振り返り
思ったより迷走していたので、提出やメモ書きを元に、振り返り(垂れ流し)。
1日目
- 問題を読む
- seed=0、これはスライドパズルっぽいし、BeamSearchが有効そう？
- 直前にAHC011の復習にn-puzzleソルバーをBeamSearchで書いていたので、ソルバーをちょっといじって動かしてみる
- 調整、高速化がしんどそうなので保留
- とりあえず、問題特有の性質やらスコアなどを考える
- 多少異種が混ざっても大きなクラスタを作るのが良さそう
- 操作列だけど、比較的普通の探索っぽい
- 状態も、ある良い状態の近くに良い状態がある感じになってそうなので、そんなに探索空間もガタガタしていなそう
- 普通にBeamSearchや山登り/焼きなまし系でいけそうか？
- 「移動の最適化」と「接続の最適化」がある
- 移動が決まったら、盤面に対してスコアが最大になるクラスタをフローとかで求められないか？
- 異種がからんでくると難しそうだし、異種を無視すると全然作れなそう、、、
- 疎なときはどかしてつなぐとかはできそうだけど、密はスライドパズルしないといけなそう
- 想定解は、疎なとき焼きなまし、密なときBeamSearchとかだろうか
- クラスタは木でよさそうだけど、木だと接続の仕方次第でカバーしきれないケースもありえる？
- 木じゃなくて領域でもって、あとで木にするとか
- というか、移動に文脈があるのに、焼きなましできるのか？
- クラスタの接続/切断で差分更新できるか考える→できそう。クラスタの種類ごとの個数がわかればO(K)で求められる
- クラスタの走査も含めてO(N+K)
- 移動操作をどうするか？
- とりあえず、greedyに復元できるか毎回試してOKな移動だけにすれば(遅いけど)できそう
- または「1手だけ動かす」でも壊れなそう
- 探索空間を狭めてしまうけど、良い解があるなら全然ありっぽい
2日目
- いろいろ考察
- 疎なとき向けに1手制約の盤面を状態に持つ自明な焼きなましを書く&調整→提出182k
- うーん
- 悪くはないけど、ここのまま進めてよさそうか判断し難い
3日目
- RiJを見ながら焼きなましを改善
- 遅いけど毎回チェックする方式で2手以上動かすようにしてみたけど、あんまり改善してなさそう
- 特定の向きに同種のサーバがあったら他のサーバを押しのけてでもつなぎに行ったほうが良いかも
- 近傍を追加→183k
- ビジュアライザを見ると、接続の仕方次第では繋げられるサーバがある
- 接続の繋ぎ変え近傍を追加→213k
- パラメータを調整→231k
- いい感じ、、、？
- seed=0(K=2で密)の改善を考える
- スライドパズル的に分離してつなぐ、ができればいいけど、移動の余裕もないので、理論値は無理そう
- 密すぎて異種を混ぜずに最大取りに行くのも厳しい
- うーん
4日目
- 焼きなましをもうちょっと詰めたい
- Kが大きいと移動に使える回数の割合が増えるので、Kでパラメータを変更→提出232k
- コードを読み返す、バグ発見
- バグ修正→289k
- 結構上がった！
- パラメータを調整→291k
- これはいけるか？
- 公式ビジュアライザは元の位置がどこから移動したのかわかりにくいので、ビジュアライザを作ることに
- 何で作ろうか考えたけど、結局1枚絵でよいので、適当にgnuplotで出力
- ビジュアライザをじっと睨む
- とりあえずバグってるのを発見
- いろんなケースを見ると、ルールベースでできそうな改善点が見つかる
- 異種サーバを取り除けそう(どかす＋もってくる＋接続)
- ちょっと離れたサーバを持ってきてつなげるのもできそう(もってくる＋接続)
- 手で計算してみると、数百点ぐらいは普通にあげられそう
5日目
- とりあえずバグ修正→298k
- 300kまであと少し！
- あ、時間のばせば300kのるか？
- 2.9秒を2.95秒に変更(せこい)→300k
- やったー
- ルールベースの実装をどうするか考える
- 面倒になって適当に書き始める(後に後悔)
- バグりまくる、再実装しまくる
- つらい(後悔)
- がんばって不純物を取り除くルールだけ書いた→304k
- 微妙、、、
- とりあえず、ビジュアライザを眺める
- 1番大きなクラスタがどういう形になるか次第で、2番目以降のクラスタが大きくなれないケースが結構ある
- 同じseedでもスコアがかなりブレる
- 大雑把に、どの種類が最大のクラスタかで、K個ぐらいの大きな山があって、どれを登るかは現状だとランダムに選んでしまっている
- いろいろ試す
- あんまりうまく行かない
- 一旦整理→310k
- 山間を行ったり来たりできる巨大近傍を検討するのが良さそうか、非自明な焼きなましを考えるべきか、そもそも焼きなまし以外か、、、
- 頭を一旦リセットするためABCにunrated参加
- 黃パフォでた、、、なぜunratedに、、、
6日目
- 一旦、後回しにしていた離れたサーバーを持ってくる処理を実装→311k
- ここもいろいろ最適化の余地がありそうだけど、伸び幅はそんなになさそう
- それよりも焼きなましの改善のほうが効きそうか
- 巨大近傍を考える
- 特定クラスタの全接続削除をして、他のクラスタを大きくするような近傍をやりたい
- ランダムに他のサーバをつないでみたり、ミニ山登り/焼きなまししてみたり、評価関数を変えてみたり、、、
- 同程度のサイズの別のクラスタを作るのが結構しんどい
- あまり重い処理になってしまうと近傍としてはうれしくない
- 全接続削除近傍だけでも少し伸びてたので一旦提出→315k
- いろいろ試す
- うまく行かず
- 考えながら、バグ修正やパラメータ修正など→327k
7日目
- バグ修正、パラメータ修正など→331k
- うーん
- いろいろ手がついていないところが多い、、、
- 現状の焼きなましは、一番大きくなれる山を選べるようにするか、巨大近傍がないと厳しい
- 密なケースも手がついていない。やはりBeamSearch(移動制限なし)のほうが良さそうか？
- BeamSearchを再度書いてみる
- 工夫しても実行時間が厳しい、焼きなまし解に勝てない、、、
- 残り時間もないし、焼きなましに絞る
- 良さげな巨大近傍が作れない、非自明な焼きなましも今から大きく変えるのも結構厳しい
- 思いつく近傍を入れていく
- 近傍を追加、高速化→346k
- ここらへんが限界か
最終日
- 微修正→348k
- なにもわからん
- ぼすけて
- 手元で試していた2000ケース、seed=1〜2000を使ってしまっていて、システムテストでは(N,K)を20個ずつなので、揃っていないことに気づく
- しまった、、、
- データを見てもそんなに偏ってなさそうで、データを作り直してみるがそんなに変わらなそうで一安心
- 1ページ目に入れてるけど、いろいろできていないところも多いし、近くの順位の人もバンバン伸ばしてて、1位のスコアを考えると普通に抜かされそう
- 最終日なので、さらに未提出だった強い人が上がってくると思うので、あとはどこまで耐えられるか、、、
- ・・・
- あれ、思ったより耐えてそう？
- 実行時間を伸ばすとスコアが上がるので、やってなかった高速化だけやって終わろう
- 高速化→351k
- ぎり350kこえれたやったー
- 終了('A`)
- 順位はよかったけど、結局焼きなまし1本になってしまったし、巨大近傍は入れられなかった、、、
- 感想戦
- 山を高速で登るのを繰り返せればよかったのか、、、
- 焼きなましも全然まだ考える余地があった、、、
- 復習して、考察の手数を増やして次回以降に活かしたい
