AHC017 個人的まとめ

久々にヒューリスティックコンテストに参加したので個人的なまとめをブログに残そうと思います。
主観のまとめなので、うるせぇ決めつけんなと思われた方にはすみません（予防線）。
古のマラソンランナーなので古臭いかもです。
6位でした。

問題文

参加されていない方はそもそも見ないと思うのでリンクだけ貼っておきます。

使用禁止な辺をグループ化して、それぞれのグループでの全点対最短経路の和を最小化する問題です。
atcoder.jp


事前に知っておくこと

マラソンマッチにおける枠組みは極論すると1つで、以下のものです。

  1. 初期解を構築する
  2. 初期解を改善する

1が支配的な場合は構築（人が考える賢い解を実装したもの）問題か、ビームサーチ（探索を適切に行って解を構築する）問題です。

1と2がいい塩梅に交わると、初期解構築（そこそこ賢い解を作る）+山登り法（解が改善する変形を繰り返す）が主なツールになります。

2が支配的な場合は、初期解構築（割と適当でいい）+焼きなまし法（解の悪化を許容して変形を繰り返す）が主なツールになります。

焼きなまし法については大昔の自分の記事があるのでリンクだけ貼っておきますが、それぞれググればわかりやすい記事がヒットすると思います。

gasin.hatenadiary.jp

問題を見て思うこと

　時系列性（Aの後にBをするのとBの後にAをする差）がないことや、遷移（この問題の場合辺の割り当て日を変更すること）が単純であることから焼きなまし法が強い解法だと感じます（僕は）。
　しかし、問題の制約を見ると遷移の計算が重く、焼きなまし法も難しそうだと分かります（焼きなまし法が強い条件として、多くの遷移が行えるというものがあります。個人的な目安は、変更対象の変数の数（今回の問題では辺数）の10倍ぐらいの試行が最低ラインです）。
　ここで、考えられる方針としては以下のようなものになります。

  • スコア計算の精度を犠牲にして、焼きなまし法を頑張って回す
  • スコア計算を頑張って初期解構築に本気を出す（残り時間で山登り法を行う）
スコア計算の補足

　今回の問題はスコア計算が重く、それをどれだけ効率よくやるかが焦点ではありました。
　高速化の詳細は問題固有ですが、差分だけを見るようにするのが基本的な部分だと思います。

　とはいえ、今回の問題は高速化を頑張っても重い場合があり、多少さぼる必要があったようです。
　スコア計算をサボるのはよろしくないことが多いですが、仕方ない場合は近似をします。
　時には統計的な手法が有効ですが、ランダムにサンプルして平均を取るのが楽です。
　今回の問題では、グラフの頂点を削ったり（1位の方など）、全点間最短距離の始点を削ったり（2位の方や僕など）するのが有効だったようです。

問題に取り組んでみて思ったこと

　スコア計算を犠牲にして焼きなまし法を頑張って回すのは（僕の手元では）得策に見えませんでした。
　焼きなまし法には良くも悪くも工夫の余地が少ないため、実行時間を数倍にしても改善の兆しが見えなかったら方針が悪いことが多い印象です。
　
　ということで、僕はスコア計算を頑張って初期解構築に本気を出すということに注力しました。
　初期解の構築と言っても、ビームサーチのような探索手法を使う計算時間的な余裕はなかったので、どのようなルールで貪欲法を回すかを人が決めるパートが本質だったと思います。
　僕は「少ないサンプルでシミュレーションを回して、影響度が高そうな辺から順に日付を割り振る&時間に余裕がありそうだったら変更があった辺と隣接する辺の割り振りの変更を試す」をベースとした貪欲法を使いました。
　1位や2位の方も貪欲法が解法のベースですが、それぞれ評価関数（見る辺の順序を決める）に、残りの辺の残数を使っていたり、ヴィジュアライザを観察した結果を評価関数に組み込んでいたりと賢い工夫をされていました。

　また、徐々に計算を真面目にやるというのも大事だったようです（1位の方や2位の方、僕も使いました）。
　今回の場合は、ある辺をどれかの日に割り当てることになるのですが、見込みのなさそうな日はスコア計算の初期段階で捨てるというのが考え方だと思います。

敗因

　貪欲パートが本質だと薄々感じながらも、賢い貪欲が思いつかずに高速化（少しでも速くなればスコアは上がるが、実行時間を数倍にしても上位に勝てなそうなら見込みが薄い）に走ってしまいました。
　重要そうなパラメータ（この場合辺の残数など）を評価関数に組み込む力が必要だなと勉強になりました（optunaとか使えると便利そうです）。

久々の長期コンの感想

　社会人での長期コンの参加しんどさと先人の凄さを感じました。
　楽しいことに間違いはないので、またタイミングが合えば参加したいです。

参考リンク

1位の方の解法（スレッド）


2位の方の解法