はじめに
AHC017（AtCoder Heuristic Contest 017 THIRD プログラミングコンテスト 2022）お疲れ様でした。念願の初青パフォをキメて入水できたので私にとっては大満足のコンテストでした！
今回の問題ではスコア計算の重さに苦しめられた方が非常に多かったようですね。それでも上位勢の方々は代表点の選定やスコアの差分計算など様々な工夫を凝らして山登り法や焼きなまし法をうまく適用していたようです。
しかし悲しいかな、私はしがないアルゴ茶コーダー。高速化の勘所なんて分かりません。そこで今回は思い切ってスコア計算を完全に放棄してみました。
本記事ではスコア計算を一切せず、アルゴリズムもごく初歩的なものしか使わず、実装面で難しいところも特に無い、そんなお手軽ながらそれなりに良い成績（提出者994人中194位、1712パフォ相当）を出せる解法を解説します。
名付けて最短経路クラスタ解法（ちょっとカッコつけました...）です。
概要
最短経路には（少なくともこの問題においては）以下の3つの性質があるっぽいです。これらを利用します。文献でちゃんと確かめたわけではないですし、私が何か勘違いしているだけの可能性もあります。あくまで「ぽい」であることをご了承ください。
※ランダムに選んだ2点のペアとその2点間の最短経路を多数生成しているという前提で
今回利用するのは性質2と3です。1についても上手な使い方があるのかもしれませんが、私はうまく活かせませんでした。
性質3が成り立つ理由については正直なところ正確に理解しているわけではないのですが、おそらく以下の2点だと思われます。
- 工事の影響を強く受けてしまう最短経路を絞れる
- 上位陣が使っていた工事辺一本道作戦に近い形にできる
ビジュアライズしてみると、工事辺が一本道に近い形で密集していることが分かります。※ここでは見栄えを優先して、かなりうまくいったケースを採用しています。
工事辺付近以外の点（紫の点）をクリックしてみると、工事の影響が小さいことが分かります。ほとんど青（影響なし）ですね。
工事辺上の点をクリックしてみた例がこちら。流石に影響が大きいものの、その範囲が限定的であることが分かります。
具体的な手順
※各工程の時間配分は私の愛用言語であるCrystal（静的型付けで高速なシングルバイナリを吐ける見た目はRubyっぽい言語、ただしC++よりは基本的に少し遅い）で実装することを前提としています。他の言語の場合は適切な時間配分が異なるかもしれません。
- 乱択で2点のペアを大量生成し、2点間の最短経路をダイクストラ法で求める。この際に各ペアに番号をつける。この番号をクラスタ番号とする。各辺が所属する（※複数所属可能）クラスタ番号を格納する配列を用意し、最短経路においてその辺が使われる度にクラスタ番号を配列に追加していく。この工程には1秒使用する。
- 各辺が他の辺と共に所属するクラスタの数を記録していく。
- 一日あたり（辺数 ÷ 工事日数）個の辺を適当に割り振り、初期解を作成。
- 2つの工事日をランダムに選び、両日からランダムに選ばれた辺を交換する。それによって各日の工事辺同士が共有するクラスタ番号が増えるなら交換を確定し、そうでないなら戻す。この工程には0.7秒使用する。
- 2つの工事日をランダムに選び、一方の工事日からランダムに選ばれた辺をもう一方の工事日に移す。移された日の工事辺同士が共有するクラスタ番号が増えるなら移動を確定し、そうでないなら戻す。この際、一日あたりの工事可能辺数の制約を超過しないように注意する。また、辺を移しすぎるとスコアが悪化するため、辺の増減可能数に制限を課す。この工程には0.3秒使用する。
- このままだと到達不能点ができてしまうので、各日の工事辺上の2点に対してDFSを用いて到達可能性を調べ、到達不能な場合は他の日とランダムに辺を交換して到達可能にする。この工程には念のため余り時間のほぼ全て(3.8秒)を使用する。
- 各辺の工事日を格納した配列を文字列化して出力。
※なお、工事日数が少ない場合（工事日数6日以下）はこの解法が逆効果になるケースが多いため、乱択で各日の工事辺同士の距離を伸ばした上で仕上げに到達不能点を解消するのみとする。これは上位陣の一本道作戦とは逆のアプローチであり、極端に悪いスコアは出ないものの良いスコアも出なくなってしまうため、改善の余地あり。
私の実装はこちら。コード自体は汚いですし命名センスが致命的に無いのがお恥ずかしいのですが、一応コメントは多めにつけているので是非読んでみてください！（やっぱり恥ずかしいから読まれたくないかも...）
この解法のメリットとデメリット
メリット
- 何の工夫も無い教科書的なダイクストラ法とごく普通のDFS程度しか使用しておらず、アルゴリズムの知識が少なくても容易に実装可能
- スコア計算が不要
- 工事日数が多く頂点数および辺数が多いほど強くなる（おそらく最短経路パターンの多様性が高まるから）傾向があり、これは1位を含む最上位陣の多くとは真逆なため、相対スコアが伸びやすくなる ※コンテスト中に工事日数が少ないケースにバグを含むコードを提出してしまい絶対スコアが大きく悪化しても相対スコアへの影響が非常に小さかったことから、この事実にコンテスト中の時点で薄々感づいていたことを自慢させてください
デメリット
- この解法をベースにさらなる改善を施すことが困難で、局所解的な性質を持ってしまっている
- 工事日数が少なく頂点数および辺数が少ないケースに極端に弱い（特に前者は致命的に悪影響を及ぼす）ため、絶対スコアは悪くなりがち（コンテスト後に確認してみたところ、私より順位がかなり低い方々にも絶対スコアでは負けていることが少なくなかった）
Wladimir Leiteさん（wleite）が作成してくださったこちらの表を見ると、私の解法が工事日数の多さに強く依存していることがよく分かります。
おわりに
解法の多様性はヒューリスティックコンテストの大きな魅力だと思います。
たとえば一言に焼きなまし法と言っても「何を良い状態と定義し、どう遷移させ、如何に高速化するか」にはたくさんの選択肢があり得ますし、その過程で使用する典型アルゴリズムや名も無き即興アルゴリズムの組み合わせは十人十色です。
また、焼きなまし法が多くのコンテストにおいて強力で最上位勢の解法で多用されていることは確かですが、それ以外にもそこそこ強いヘンテコな解法を生み出す人がいたり、結果は伴わずとも面白い特徴を持つ解法を生み出す人がいたりして、コンテスト後のTwitter競プロTLは同じテーマの元で個性的な絵を生み出す合同展の様相を呈しています。
結果の良し悪しに関わらず、参加者全員の解法に強みや弱み、そして面白みがあるんじゃいかと思います。それがTwitter上での刹那的な消費で流れてしまうのは何だかもったいないので、もっと多くの方がご自分の解法を記事として書き残して頂けると嬉しいです！
