こんにちは。競技プログラミングをしているssaattooと申します。HACK TO THE FUTURE 2024 （AtCoder Heuristic Contest 027）に参加して 10位でした。
反省、または誰かの為になることを期待して参加記録を残します。
問題概要
グリッドの原点から始めてすべてのマスを１回以上通って原点に戻ってくるようなルートを作成し、そのコストを最小化してください。ただし、各マスには訪問と訪問の間隔により異なるコストがかかります。
解法
大まかな解法は以下の通りです。
- validなルートをdfsにより生成し、これを初期解とする。
- ルートを部分的に破壊して再構築する焼きなましをする。
これで暫定テストで96.9%程度の点を得られます。
初期解の作成パート
訪問順をランダムにしたサンプルプログラムを100回実行して、最も素のスコアが高いものを初期解として採用しました。
おそらく初期解が最終スコアに与える影響は大きいのですが、良い方法が思いつきませんでした。
焼きなましパート
ルートの一部の区間を別のものにすることを近傍とする焼きなましをしました。近傍の詳細は、
- ある区間を１つ選び、dfsで作成した新しいルートに変更する（95%）。
区間幅1-50程度の区間を選択し、区間幅1-7程度のdfsで作成した新しいルートと交換しました。dfsでは関節点以外の点の訪問は１回までに制限し、関節点は何回の訪問可能にしました。 - 最初と最後のマスが一致する区間を２つ選び、これらをスワップする（1%）。
マスp0..=p1という区間が２つあった時、これらを交換してもvalidな状態は保たれています。 - 最初と最後のマスが等しい区間を１つ選び、これを反転する（4%）。
マスp0..=p0という区間があった時、これを反転してもvalidな状態は保たれています。
です。
スコア計算が重いので差分計算を頑張ります。計算は合わなかったけど、焼きなましのイテレーション1000回ごとに正しいスコアに直したら問題は起きませんでした。数十万から数百万回イテレーションできました。
差分計算
ある区間が変化したときの、その区間の中で閉じている部分のスコア差分計算については省略します。
差分計算で重要だったのは、変化した区間と変化していない区間にまたがる部分のスコアでした。特に区間の変化によって長さが変わるときに複雑になりました。
図１のような、4個のマスがありルートの長さが10であって、ターン６とターン７の間にルートが挿入されることを考えます。その時各マスのスコアは(訪問間隔×d)だけ増加します。全マスにおけるsum(訪問間隔×d)=xとすると長さがL増加するときは、x*L + (L-1)*L/2 * sum(d)となります。逆に縮むときはx*L - (L+1)*L/2 * sum(d)に近いです（あるセルの区間がL未満だった場合はおそらく誤りです）。
各ターンにおけるxを事前に計算しておくことで、計算を高速化できました。事前計算には経路の長さ分だけ時間がかかるのですが、焼きなましの受理率が数%であったため、受理されるたびに計算しても問題ありませんでした。
その他の工夫
- ルートの倍化。
実行時間が半分過ぎたタイミングとラスト付近で、ルートを同じものを2個つなげました。こうすることで、dが小さく訪問頻度を下げて良いマスを消去しやすくなることを期待しました。実際に当時のスコアで6%ほど改善しました。
日記
メモなので汚いです。
クリックで詳細表示
目標
最低限の取り組む時間で黄上位程度をめざす。考察してある程度の根拠をもって実装する。きれいなコードを書く。
コンテスト１日目
問題を読んだ。得意そうなやつで嬉しい。
ルートにループする動きを追加した場合、汚れの大小関係は変化している場合があるので、少し文脈がある。
コンテスト２日目
ahc024みたいに期間が重要かも。
シンプルな部分破壊焼きなましを書いて11位。この問題は評価関数と高速化ゲーになるのでは。
探索効率が悪いので、再構築時は同じところの訪問を禁じるか。それでも折り返しなどを保てる？
ルートで座標p0..p1という区間が２つあった時にそれらをスワップする近傍を追加して１割くらい点が伸びて45.6億で７位。
p0..p0という区間を反転する近傍を追加で46,6億で５位。
実行時間を10倍にできたら数%伸びるので1位くらいのスコアは出る。スコア計算が重い。とりあえず未訪問のマスがあるときは計算しなくする。
初期解をサンプルのままにしているけど変えたい。いい貪欲とはなんだろう。
盤面の平均より大きいものを消せばいい？
動きの長さは短いほうがいいのか？
コンテスト３日目
bitset高速化？
dが小さいマスを何回も通る必要はない。繋ぎなおしはdfsではなく、dが多いところを通るダイクストラ？
未訪問期間の寄与が最も大きいマスをなんとかする。
受理率が数％なので、意味のある候補を生成したい。
確実に前進するような、繋ぎなおすときの貪欲はあるかな。あれば山登りキックでいい。
コンテスト４日目
平均aよりaが小さいマスを１手追加して踏むことで改善することは絶対にない？一度のみ訪問するマスの平均コストはd*(L-1)/２。dが小さいマスを訪問する回数を減らし、dが大きいマスの訪問時期を分散させることが重要。
一筆書きよりは小さくしたい->さすがに一筆書きよりは数割良かった。初期解はできるだけ一筆書き->dfsの方が強い。
ビジュアライザにマニュアルモードを追加する。ビジュアライザをマニュアルモードで１手ずつ更新すると重すぎるので差分計算できるように自作する。
Lが無限であるとき、理想はdの比率で訪問を均等な間隔ですることが理想だと思う。現実ではdが大きいところの間の移動距離がボトルネックになる？
倍化しても、スコアが悪くなることはない。時間が半分すぎたら倍化するようにしたら、なんと6％ぐらいコスト減少した。倍化したから区間削除も追加する->伸びない。
10倍速にできると、49.1（2位相当）はでるらしい。
コンテスト５日目
被覆問題？
差分計算しようとすると、stateの更新ごとに必要なデータの更新が重くなってボトルネックになってしまう。いいデータの持ち方を考える。
スコア計算は頑張ればO(変更された長さ)で可能だけど、そのデータの更新に結局O(L)かかってしまう。データ更新もO(変更された長さ)でできるかもう少し考える。
閾値で枝刈り。
でかい幅でswapとかが成功していないなら、幅を縮める。
反転は差分計算が簡単。
今46.0で15位。5倍速にできたら47.9で4位くらいでるのに。
コンテスト６日目
changerouteでももとの長さと新しい長さが同じになることが1/10くらいである。これは差分計算が簡単にできる。
差分計算をバグらせまくり。明日完成させる。
コンテスト７日目
伸ばすときのコストはあっているっポイ。
dna。
今のままだと、行き止まりを往復するようなものはあらたに生成されないので、コピーして挿入する近傍を作る。
ばぐとれない。スコア合わないまま使ってみたけどそんなに早くならない。
コンテスト８日目
47.5で13位相当。
焼きなましの受理率が1%くらいなので、いい近傍を列挙できていない。
スコアはnかn^2で割ってそろえる？sum(d)をそろえた方がいいと思ったのでsum(d)=100000となるようにdを調整した。まあまあ伸びた。
dfs中で未訪問があったらng。
48.42で7位相当まで来た！もし５倍速にできたら2%伸びるので、49.39で2位相当になるらしい。
penalty設定してないけど何かいいのあるかな。最初の方は長さが（長いor短い）ほうがいいみたいなのか？
コンテスト９日目
nと壁の個数ごとにパラメタ調整あとでする。多点スタート。キック。スコア計算を閾値で枝刈り。
ラストに詰めの貪欲で短くできるか。
10個近傍をつくって最もいいものを必ず受理する？
前回変更された近傍の近くは改善の余地がある
dfs中で大まかにスコア計算して、あまりにもあり得ないやつはngにする。->適当なやつだと判定できなかった。
nと壁でスコアを整える
なにも伸びない。明日やること。整理。スコアの調整。パラ調整。
コンテスト10日目
受理されたときだけ正確なスコアにする？
提出。48.68で10位。あと0.5%伸ばしたい。
初期解は本当にdfsでいいのか？
提出48.791で8位。
usizeを32にするとはやくなるか？dfsを非再帰に？
最終提出上振れて48.46で9位。
終わりに
良かった点
- 実装する時間を少なくできた
- 焼きなましに落とし込むことができた。
悪かった点
- 考察する時間は増えたけど、数学的に理解することはできなかった。
- コードが汚い。
- 初期解やスコアの標準化など詰めが甘いところがあった。
Todo
- 焼きなましの構造体を改良してもう少し使いやすくする
- Optuna用にコードを書き換えたりするのが面倒で結局手動でパラメータ調整をしたため、Optunaに慣れておく or マクロなどで対処可能なようにする？
- テストを書く
感想
焼くだけにしかみえなかったので、HTTFらしくない問題だなーと思っていました。実際はもっと奥深い問題だったらしく、捨象して典型問題に落とし込めているのはいいけれど、細部まで考慮しないと最上位には届かないかもしれないと痛感しました。
過去最高順位でやったーという気持ちはあるけれど、満足のいくまで取り組めたとは言えないので今後の課題としたいです。
来年も10位以内に入って本選に行きたいです。
