はじめに
本記事は、先日行われたTHIRD プログラミングコンテスト2025(AtCoder Heuristic Contest 045)の参加記です。
最終スコア2589G(プレテスト43.5G)、29位という結果でした。
以前書いた【競プロ】ヒューリスティックコンテストで戦うヒントの"実践編"として、今回は実際に どのように問題に取り組み、どのような作戦を立てたのか にフォーカスして紹介します。
問題概要
- 800個の都市を指定された都市数のグループに分けたい
- 各グループ内の都市を道でつないで連結にしたい
- その時の道の長さを最小化したい
- 各都市の位置は正確にはわかっておらず、存在範囲が矩形で与えられる
- 400回まで、L(3〜15)都市以内の都市を選択して「占い」を行うことができる。占いでは選択した都市の最小全域木がどの都市間を結ぶ道かがわかる
インタラクティブに占いを行いつつ、指定された個数へグループ分けするという、全体的に要素盛りだくさんの問題です。
詳細は公式サイトをご覧ください。
問題への取り組み過程
序盤
貪欲でグループ分け
問題の要素が多く、どこから手をつけるべきか悩みました。こういう場合は「ヒント2 小問題に分割する」の通り、問題を分割したいところですが、全体のロードマップも見えません。また占いのアウトプットも独特すぎて、どう使って良いのか見当もつきません。
仕方がないので解として成立させる最低要素として、初手はグループ分け部分に専念することにしました。
- 都市は与えられた長方形の中心にあると仮定
- 与えられたグループの順番で、指定された都市数のグループをプリム法で構成する
- 起点となる都市はその時点で残っている中心から最も遠い都市とする
2個目の条件は、無闇にプリム法で作っていくとバラバラの都市が残り、最後の方のグループで都市間が長くなりすぎることが予想されたため、その対策です。こうすることで、最終的に真ん中あたりの都市が残って、うまくまとまるのではないかと期待しました。
以下はseed=7の結果です。まずまずの形にはなっているものの、赤丸で囲ったような長い道ができてしまっています。グループ構築過程で、一部の都市が取り残されてしまっているのだろうと想像されます。
これを改善したい気持ちはありますが、他の要素も多いので、いったん後回しにして次に進むことにします。
占いを使って結果を改善
ここまでは占いを一切使っていませんでしたが、何か使い道を考えないといけません。薄々は都市の位置を推定するのに使えるということなのだろうと思いつつも、この時点では具体的にどう使えば位置推定できるのか全く見えていませんでした。
しかし、最低限のグループ分けができたことで、作成したグループ内の最小全域木を占い結果で改善できることに気がつきました。木に含まれる部分木に対して占いを行い、その部分木を構成する辺を占い結果で置き換えても木構造は保たれるはずです。そして、その部分木は確実に改善することになります。
この後、簡単に取り入れられそうな以下の工夫を入れました。
- 誤差の大きい点から優先して占う
- L以下のグループは最善の最小全域木が確定するので、1回占ったらそれ以上は占わない
- L以下のグループを優先して占う
この程度の占いの使い方でも、何もしない場合と比べるとスコアが35%くらい改善することがわかりました。
中盤1
全体の最小全域木からグループを切り出す
ここまでで、多少の欠点はあるものの、それなりのグループ分けと簡単な占いの使い方がわかりました。
今後は占いによって都市の位置推定を行なっていく方向になると予想しているものの、この段階ではまだ方針が定まっておらず、グループ分けの結果も長い辺が残ってしまう問題があったので、グループ分け方式の見直しに着手することにしました。
現在の方法の欠点は、順次グループを作っていく過程で孤立した点が残ってしまうことだと思われるので、先に全都市で最小全域木を作ってしまってから、辺を削除してグループに分けてはどうかという考えに至りました。構成できるグループ分けがかなり限定されてしまうものの(「ヒント3 自主的に制約を追加する」)、極端に長い辺が出てこなくなることが期待されます。
ただし、この発想には重大な問題があることにも気がつきました。
全体の木から辺を削除して分割するスタイルでは、どうやっても分割できないパターンが存在しうるということです。
成立する解に到達できないと困りますが、最悪失敗したら元の方法を採用することもできますし、失敗頻度もやってみないとわからないので「ヒント8 嘘解法でも良い」「ヒント7 コーナーケースに囚われすぎない」の精神でまずは試してみることにしました。
分割できない可能性があるのは問題ですが、逆に「ある辺で分割可能かどうか」は動的計画法(DP)で正確に判定できます。さらにどのグループを割り当てれば良いかもDP復元で解くことができます。(「ヒント4 アルゴリズムの知識で解ける範囲を探す」)
この方法を実装してみた結果、残念ながら大半のケースではどこかで分割に失敗することがわかりました。
多少何かを変えてやり直したところでうまくいく頻度でもなさそうだったので、失敗した場合は木を一度破壊した上で、強制的に都合よく二分割して、それぞれで最小全域木を作り直すという処置を入れることにしました。
強引ではありますが、これにより必ずグループ分割が成立するようになり、スコアも2%程度改善できました。
分割する前に占う
この時点でのビジュアライザを見たところ、以下のようなケースが気になりました。
青い正方形は赤丸の都市について事前に与えられた存在範囲です。この都市は今所属しているグループではなく、近隣の別のグループに所属させた方が良さそうです。
現状の処理は以下の通りです。
- 正方形の中心にあると思って最小全域木を構成
- 辺を切ってグループ分け
- 各グループの部分木で占いを行なって、グループ内の最小全域木を改善
この手順では、正確な位置が分かっていない段階でグループ分けが行われ、分けられたグループの範囲内で改善されているという状況になります。
そこで、最初の全体の最小全域木の状態で占いを行なってから分割を始めることにしてみました。その方がより最適なグループに分けることができるのではないかという仮説です。
これを実装してみると、また1〜2%程度改善しました。
中盤2
都市の位置の推定
ここまで薄々は必要だと思っていたものの先延ばしにしてきた都市の位置推定ですが、グループ分けがある程度できるようになってきたので、取り掛かることにしました。
まず、占い結果で得られる最小全域木から、どんな情報が得られるのかについて考えてみました。
例えばある都市Pに着目し、最小全域木でPに隣接する都市のペアA,Bがあるとすると、以下の関係が成り立つことがわかります。
- dist(P, A) <= dist(A, B)
- dist(P, B) <= dist(A, B)
もしこれらが成立しない場合、A-B間の道が採用されているはずだからです。同様に、Pから見てA配下の部分木の都市Xについても以下が成り立ちます。
- dist(P, A) <= dist(P, X)
つまり周囲の都市の位置がわかれば、Pの存在範囲を絞り込むことができるというわけです。これまで使ったことがない手法ですが、ギブスサンプリングのような形で都市の範囲が絞っていけるのではないかと考えました。
しかし、制限時間を考慮すると、大量のサンプリングもできそうにないので、あまり細かくすることは諦めて、最初に与えられる都市の範囲を2×2の4領域に粗く分割し、各領域の中心点が正解である確率を比較するというアプローチで進めることにしました。(「ヒント1 粗視化する」)
- 各都市の存在範囲を4分割し、等確率としてサンプリングする
- 1都市に着目し、他の都市が正しい位置にあると仮定したとき、距離関係が成り立っているかを検証する
- 判定は「成り立つ/成り立たない」の2値ではあるが、全部が成り立つケースも少ないと予想されるため、距離差をシグモイド関数で0〜1の値とし、尤度とみなして扱う
- この尤度を更新し、尤度比に基づいてサンプリングし直す
- 尤度の差が一定以上になった場合、その領域をさらに4分割する
この方法を実装してみたところ、サンプリング数や更新回数を数回程度に制限すれば、現実的な時間で実行可能でした。そして、スコアも2〜3%改善しました。
また、一度投げたクエリは覚えておいて、同一クエリを投げないような処理を追加したところ、思いの外効果があり、さらに1%程度改善しました。
全体構造の整理
都市の位置推定がある程度できるようになり、一通り取り組むべき要素が出揃った感があったので、ここで一度今回の解法の全体像を整理してみました。(★は占いの回数を消費するステップ)
「ヒント2 小問題に分割する」の分割がやっとできました。この後は、各ステップの改善や、占い回数の配分検討といった調整がメインになると予想されます。
それに備えて、今後の実装や試行錯誤を進めやすくするために、大規模なリファクタリングを行いました。「ヒント10 拡張性は後回し」ですが、方針がある程度固まった段階でのリファクタリングは、今後の改善のやりやすさの観点からむしろ積極的に行うべきだと考えています。
終盤
実行条件の調整
今回の解法では、占い回数(最大400回）を消費するステップが3箇所あるため、どのステップで占いを使うのが良いのか実験してみることにしました。
パラメータの種類が多いので、傾向を見るにはある程度のケース数が必要と判断し、システムテストと同様の3000ケースで比較することにしました。結果をwataさん作成のローカル順位表ツールで可視化してみます。
- 青：都市位置推定(Step.1)に全振り
- 赤：全体の最小全域木改善(Step.3)に全振り
- オレンジ：グループ分け後の最小全域木の改善(Step.5)に全振り
※このグラフは実施当時ではなく、コンテスト終了後に再作成したものです
- Lによる優劣
- Mによる優劣
この2つのグラフから以下の傾向が見えてきます。
- 1つ目のグラフ
- L<=6では赤が強い
- L>=7では青が強い
- L=3のでは赤とオレンジの差がほとんどない
- 2つ目のグラフ
- 青と赤の比較では全般的に青が強い
- 赤とオレンジの比較では赤が強いが、Mが小さいほど差が縮まっている
さらに、L=3に限定してMによる優劣を詳しく見てみました。
- Mによる優劣(L=3の場合)
微妙ではありますが、M<=150〜200ではオレンジの方が強いことが見て取れます。
この結果を踏まえて、L,Mの値によってStep.1やStep.3の実行有無を切り替える処理を加えました。
細かい改善
ここまで来ると、改善を試みてもスコアが上がらないことが増えてきます。「ヒント9 一歩ずつ進める」の通り、改善要素は1つずつ試して、実際に改善したものを取り入れていくことが大事です。
大半の試みは効果がなかったのですが、そんな中でも比較的効果があったものを1つ紹介します。
都市をグループ分けする際、誤差が大きい(存在範囲が広い)都市を下手につなぐと、想定と実際の位置が違いにより長い辺が生成されてしまうリスクがあります。そこで、そうした都市はなるべく他の都市と辺をつながず、サイズ1のグループに割り当てたり、次数1にとどめるといった対応が有効ではないかと考えました。
都市の位置推定で、都市の位置の誤差(分散)を算出していたため、Step.2で最小全域木を構築する際に、都市間の距離に両端の都市の誤差をペナルティとして加えることにしてみました(一定の係数をかけて加算)
この変更は比較的単純なものでしたが、1〜1.5%程度の改善効果がありました。
実行時間を活用する
いよいよコンテスト期間も残り1日になりました。
この時点でもまだプログラムの実行時間を使いきれていない状況でした。
今回の問題はインタラクティブ推定系でありながら、非インタラクティブ要素も多く含まれており、「ヒント5 実行時間を活用する」の意識を持って取り組む必要があると感じました。
最初は都市位置推定時のサンプリング数を増やすなど、推定パート(Step.1)で時間を使おうと思ったのですが、時間管理が難しい上、効果も薄かったので、グループ分けパート(Step.4)での時間活用を考えました。
Step.4では辺の長さ順に分割できるかどうかをチェックして、可能であれば貪欲に分割を行なっていました。しかし、必ずしもそれが最善とは限りません。
そこで、辺の長さの一部をたまにランダムにシャッフルして、実行時間の限り分割処理を繰り返すことにしました。
Stepが多く時間管理が複雑にはなりましたが、事前にリファクタリングしておいたおかげで、制限時間内にうまく収まるようなタイムアウト処理も実装できました。
高速化する
「ヒント6 高速化は後回し」の方針通り、ここまでは高速化にあまり手をつけていませんでした。
しかし実行時間の活用方法も決まったので、繰り返し実行することになったStep.4の部分の高速化を図ることにしました。特に、分割失敗時の強制分割処理が雑だったため、そこを中心に高速化を図りました。
その結果、繰り返し回数を増やすことができました。
コンテスト結果
冒頭にも書いた通り結果は29位で、最近の成績を考えるとまずまずだったと言えると思います。
wleiteさんによる結果一覧によると、最も悪かった領域でも39位であり、極端な弱点のない解法になっていたようです。
また、理由ははっきりしていないものの、Lが小さい場合に強い解法だったのも興味深い点です。終盤に実験の結果に従って、Lが小さい時は推定を捨ててグループ分け後の改善に占いを集中させたのが功を奏したのかもしれません。
おわりに
本記事は、前回の記事【競プロ】ヒューリスティックコンテストで戦うヒントの実践編という位置付けで、AHC045の参加記をまとめたものです。
ややこじつけ気味なものもありますが、AHC045では10個のヒント全てを使うことができました。
ヒントの使い方の具体的なイメージとしてご参考にしていただけると幸いです