HTTF2024 (AHC027)
14ヶ月ぶりに長期AHCに参加しました。
黄パフォを目指していましたが353位(perf1433)で全く振るわずでした。
コンテスト中
全体的な方針
最も近い未到達点をBFSで見つけて経路復元
同じ距離なら(未訪問頂点をUnionFindして)他から孤立しているところを優先
「1マスだけ拭いていなくて最後に戻ってくる」みたいなのを防ぐ
経路はDPで1番汚れているところを通るように
「汚れやすいエリア」を時々吹きにいく
時々の頻度は適当に全探索
焼きなましの近傍は単純な追加と削除のみ
隣接2手追加:(y+1, x), (y, x)のような
削除:(y, x)から(y, x)までが訪問済みなら削除
詳細
1. 全頂点を通る探索を効率化する
2. 汚れやすいエリアをどう回るのがいいか考察する
3. 上手い近傍を見つけて焼きなます
の3つを考えていった。3まで上手くいけば温度調整や高速化なども考える予定だったが、そこまでいかなかったので考えていない。
1. 全頂点を通る探索を効率化する
初日に自明解としてDFSを書いた。
DFSは葉以外を毎回2回通るので無駄が多い。「最後の分岐より後でより根に近い頂点に隣接しているならそこに戻る」とか、非再帰DFSにして柔軟にスタック操作する改修を入れ、スコアは改善したが結果としてこの改修時間は無駄だった。
盤面サイズは40*40で、初期解のターン数は高々数千なので「毎回未訪問頂点までBFSして、経路復元する」でよい。
未訪問頂点の探索順は難しい。「1手先の汚れがより大きいところ」という貪欲を初期に書いたが、スコアが下がった。未訪問エリアがガタガタになるので結果的に無駄な探索が増えるっぽい。1手ごとにプレイアウトも初期に書いたが1.5秒くらい使う割にスコアが伸びなかったので止めた。「他から孤立しているスペース」は後で探索しにくいので、それを優先して探索するようにした。それ以外は「上下左右」のような規則的な優先度になっていれば結果的に小学生の雑巾がけみたいな動きになってそう悪くはならない。
2. 汚れやすいエリアをどう回るのがいいか考察する
「汚いマスを雑に列挙する」「適当なターン数ごとにそのエリアだけを回るフェーズを挟む」をした。
汚いマスの列挙は暫定で「最も汚い30マスを列挙する」「その30マスの近くで汚れ150以上のマスを列挙する」で作ったものを最後まで採用した。ここをチューニングすれば多少は上がったと思うけど時間不足で着手できていない。
適当なターン数は、(一切挟まないケースと)、for (int i = 100; i <=800; i+= 20)を全探索した。
「汚いマスの近くに行った時に立ち寄る」「焼きなましの近傍に活用する」はできていない。
3. 上手い近傍を見つけて焼きなます
いろいろ検討して書いたけど上手くいかず、最終提出では初期に考えた「1マス隣に立ち寄る追加近傍」「同じマスへの閉路が全て訪問済みなら削除する近傍」だけが残った。
他には「同じマスへの閉路を反転する近傍」「2-opt」「Nマス先に立ち寄る近傍」「部分破壊して最短経路をDPする近傍」などを書いたが微妙だったので不採用にした。でも流れてくるツイートを見ると反転や2-optを取り入れている?スコアには寄与しないけど状態は大きく変化するから良いみたいなツイートを見た。
反省点
長期AHCの期間は休日を確保すべき
今回、休日が4日間とも埋まった状態でしたが、有給と合わせて3日間くらいAHCに没頭する時間を取りたいなと思うくらい掛けている時間が不足していました。平日に「23-24時に帰宅して2時間くらいAHCする」という生活をしていましたがこれでは全く足りずです。
汚いエリア優先のチューニングと近傍の手数増加に1日掛ければ青パフォ下位くらいは取れそうで、それ以上はまぁ実力不足なので仕方なしです。
進め方は割と良かった
最序盤:「自明解とスコア計算と1000ケーステストするスクリプトを書く」「使い回せそうな構造体にする」
序盤:「初期解の強化、探索、ルールベース、焼きなまし近傍をそれぞれ考えてちょっとずつ実装する」「暫定順位のための高速化やパラメータチューニングをやらない」
中盤:「日中に考えて夜実装のPDCAを回す」
終盤:「上手くいったのを合わせて最終方針にする」「少しでも改善する(時間不足気味)」
あとはupsolveして血肉にしていけば黄パフォが見えてくるはず。
コンテスト後
解説放送やTERRYさん記事にあるように「最適解でどうなるかというイメージを持つ」というのは重要そうな知見。