- 0.はじめに
- 1.目標
- 2.wataさんのコードを解析する
- 3.ギブスサンプリングについて調べる
- 4.実装
- 5.改善1
- 6.グループ分けの見直し
- 7.ギブスサンプリングの高速化
- 8.可視化
- 9.その他の挑戦（失敗したもの）
- 10.キックする
- 11.おわりに
0.はじめに
はじめまして、もしくはお久しぶりです。競技プログラミング歴6年目のかえでです。
今回は、先日行われたTHIRD プログラミングコンテスト2025（AtCoder Heuristic Contest 045）の復習記事を書きました。コンテストの開催期間は2025年3月28日(金)19:00から4月7日(月)19:00までの、11日間の長期コンテストでした。
私の成績は1298人中266位。
そこまで悪くない結果ではありましたが、推定をうまく使うことができずに終わってしまいました。
そこでコンテスト終了後にあらためて問題に取り組み直すことにしました。
1.目標
今回の復習の目標は、
- ギブスサンプリングを用いて座標推定を行う
- コンテスト中の自分のスコアを超える
ことです。
2.wataさんのコードを解析する
復習のスタート地点は、wataさんの提出をC++に変換することでした。RustをC++に書き直したので、wataさんの実際のスコアとは異なる部分があると思うのでその点はご了承ください。それでも自分よりとても良いスコアであることには違いありません。
C++にしてみたものの、最初は、
- 何をしているのか全くわからない
- どこをどう読んだらいいかも難しい
という状態でした。
なお、AHC045の解法については、AHCラジオで詳しく解説されていますので、そちらをご覧ください。
3.ギブスサンプリングについて調べる
ギブスサンプリング（Gibbs Sampling）とは、
-
マルコフ連鎖モンテカルロ法（MCMC）の一種
-
複雑な多次元分布からサンプルを得るアルゴリズム
とのこと。何を言っているのかがわからず、最初はとても難しく感じました。
ChatGPTに質問しながら、自分なりに簡単なイメージにまとめました。
-
適当な場所（初期値）からスタートして
-
少しずつ動かしていき
-
本当に欲しい分布に近づいていく
- 最終的にサンプルを使って推定や解析をする
この「本当に欲しい分布」に近づく過程を「収束」と呼びます。そして収束したあとに得られるサンプルを使って、
-
分布の形を推定する
-
各変数の平均や分散を推定する
-
何かしらの予測・推論をする
を行うことがギブスサンプリングであると理解しました。
4.実装
まずは、wataさんのコードをもとに、自分の理解できる範囲の要素を使って、クエリを推定に使うギブスサンプリングを実装します。
【実装の流れ】
-
初期位置設定：各都市の矩形の中心座標
-
クエリ選び：矩形範囲が広い都市を優先し、未使用の都市と組み合わせてL個選択
-
MSTと不等式生成：クエリ結果から不等式（距離制約）を作成
-
ギブスサンプリング：1秒間各都市をランダムに移動し、不等式違反を減らす
-
最終座標から距離行列を作成
-
都市のグループ分け・提出用出力
3.の不等式生成部分が今回のコンテストでの重要ポイントでした。
下図のA,B,Cを見たとき辺AB、辺BCはMSTで使用されている辺になります。この時、使用されていない辺ACとの間に
AB<AC
BC<AC
が成り立っています。
同様にB,C,Dを見ると
BC<BD
CD<BD
四角形ABCDを見るとADをつなぐと閉路ができるので、これが一番長い辺であるとわかります。したがって、
AB<AD
BC<AD
CD<AD
が成り立ちます。
不等式生成プログラムの疑似コードです
初期化：
ineqs = 空のリスト (生成された不等式を入れる)
order = 0〜N-1のリスト
orderを各都市の矩形の広さが大きい順にソート
done = 空のハッシュセット（クエリの重複防止）
used = N×Nのfalseの2次元配列（クエリ済み管理）
q = 0（クエリ回数）
for orderで並べた都市cについて：
cand = cに対する全都市との距離を計算し、近い順に並べる
cs = 空のリスト（クエリに使う頂点集合）
for candから順に取り出す：
ok = true
for csにすでに入っている都市jについて：
if iとjのクエリはすでにusedなら、ok = false
if okならiをcsに追加
csのサイズがLになったらbreak
csのサイズがLでなければ、次のcへ（continue）
csを文字列keyに変換（重複クエリ防止用）
if keyがすでにdoneにあるなら、次のcへ（continue）
keyをdoneに追加
es = csに対してqueryを実行（最小全域木の辺集合を得る）
adj = 隣接リストを作成
esに含まれる各(u,v)について：
adj[u]にvを追加
adj[v]にuを追加
used[u][v] = true, used[v][u] = true
for cs内のすべての都市ペア(i,j)について (i < j)：
if iとjの間にまだ直接の辺が存在しないなら：
DFSでiからjまでのパスを探す
path = iからjまでの頂点列
path上の隣接する頂点ペア(k, k+1)それぞれについて：
(a,b) = (小さい方, 大きい方)の順に並べたpathの辺
(c,d) = (小さい方, 大きい方)の順に並べたcsのペア(i,j)
ineqsに(a,b,c,d)を追加（不等式として記録）
クエリ回数qをインクリメント
if qがQに達したらbreak
図式化するとこんな感じ。
都市を矩形サイズが大きい順にソート
↓
各都市cについて繰り返す
↓
cに近い順に都市リストを作る
↓
近い都市から順に、未使用の組み合わせを選ぶ（最大L個）
↓
もしL個そろわなかったらスキップ
↓
クエリに使う頂点集合を登録（重複防止）
↓
クエリ実行 → MSTの辺集合を得る
↓
MSTの隣接リスト(adj)を作成
↓
都市集合内すべてのペアについて：
- 辺があればOK
- 辺がなければDFSでパスを復元
- パス上の辺から不等式(a,b,c,d)を生成
↓
不等式リスト(ineqs)に追加
↓
クエリ回数がQ個になったら終了
結果です。
グループ分けは雑に書いているのですが、それでもW（都市の座標が含まれる長方形の幅や高さとして有り得る最大値 ）が大きいときは、コンテスト中の自分の結果（下図左）よりもかなり良い結果が出ました。
5.改善1
単純なランダム移動だけでは限界が見えたため、改良を試みます。
【今の方法の問題点】
-
ランダムに動かすだけなので無駄な試行が多い。
-
局所最適にはまりやすい
【今の方法の良い点】
- 探索の多様性は高い
手法を調べます。
【改良方法】
① ランダムからの「近傍移動（メトロポリス的手法）」
- 方法：
ランダムに「小さく動かす」
（たとえば、今の座標から±30以内などの小さい範囲に限定して動かす） - メリット：
局所的に動くことで、評価値の変化を滑らかに捉えられる
不等式の違反が減りやすく、局所最適に早くたどりつける
- デメリット：
初期位置が悪いとグローバルに最適な場所に行けない（多様性が低い）
② ヒートマップ方式（事前に良さそうな座標をスコアリング）
- 方法：
その都市に関連する不等式の 違反が少なそうな座標 を複数スキャンしておいて、そこから選ぶ - メリット：
最初から良い候補を見つけやすい
収束が速くなる可能性
- デメリット：
事前計算が重い（たとえば100×100スキャンすると時間がかかる）
③ 勾配的（gradient-like）な動かし方
- 方法：
不等式違反の差分から「どちらに動かせば違反が減るか」を評価して、その方向に動かす
疑似的な勾配法（gradient descent）みたいなもの
- メリット：
非常に効率よく違反を減らせる（特に後半） - デメリット：
解析がやや複雑
不等式違反が離散的なので、連続的な勾配にはなりにくい
④ Simulated Annealing（焼きなまし）
- 方法：
今の方式に「温度」パラメータを入れて、
悪くなる移動でも確率で受け入れる
時間とともに「温度を下げる」ことで探索を絞る
- メリット：
局所解を回避できる
安定的に良い解に向かいやすい
- デメリット：
温度の設定、冷却スケジュールが難しい
１の近傍移動を取り入れ、範囲を変えて結果を見ます。
±100・・・あんまり変わらないかも。
±30・・・悪くなった
±200・・・少し良くなった
４の焼きなましを入れます。
うーん、変わらない。
３の勾配的移動。小刻みに良い方向に動かす
±1ずつ10回・・・イマイチ
±10ずつ10回・・・イマイチ
±100ずつ10回・・・イマイチ
採用されていないみたいなので焼きなましと併用することにします。
±1ずつ10回・・・イマイチ
±10ずつ10回・・・イマイチ
±100ずつ10回・・・イマイチ
斜め方向を入れて8方向にしてみます
±10ずつ10回・・・イマイチ
うーん…。
6.グループ分けの見直し
先にグループ分けの方に推定座標によるグループ分けを焼きなまします。これはコンテスト中も行っていてかなり良くなります。今回も良い感じ。
あ、グループ分けを焼きなましで行う際の、推定座標から求めるスコアの計算方法が異なっていることに気が付きました。隣接頂点の辺の長さの和を足していたので、MSTでスコアを計算します。
ぐーんと良くなりました！
やっとコンテスト中のスコアを超えることができました。
絶対スコアは10971749になりました。
延長戦順位表では170位になりました。（2025年4月20日現在）
あ、それにあわせてスコアの差分計算も修正しなければならないのを忘れていました。
ん、なおしたら下がった。
MSTのスコア計算が重いようです。
なので、辺の長さの差分のままにします。（都市uとvを入れ替えたときの他の頂点との距離の差分を評価する）
7.ギブスサンプリングの高速化
さらにギブスサンプリングの高速化のために、違反している不等式だけを管理することにします。また座標選択時の動かす範囲を矩形サイズによって変えることにします。
Wが2425のseed19ではコンテスト時の230091から136208になり、高速化で131917にまでスコアが改善しました。
8.可視化
推定過程を可視化するビジュアライザも作成しました。
×見づらいので却下。
作り直してみました！
×前後関係がないとわからないので却下。
移動の線を薄くして現在位置を点にします。
お、だいぶよくなってきたのかも。
真の座標も四角で追加しました。
局所改善しながら違反を減らしていく様子が目で見てわかるようになりました。
（アニメーションはフレームを間引いています）
9.その他の挑戦（失敗したもの）
- ランダムに300回試して、成功した座標を平均して新しい座標にする
あれ？スコアが悪化しました。
-
都市はランダムで選ぶ
-
50%で近傍（±100）、50%で矩形全体ランダム
-
焼きなまし確率 (
exp(-diff/T)) で悪化も受け入れる -
不等式違反が完全0になったら即終了
結果はよくなりませんでした。
- 違反を減らす山登りだったのを焼きなましに変えます
- 違反0になったら推定クエリを終了します
あれ？良くならない。
- 正三角形＋エントロピー方式でクエリの頂点を選ぶ
スコアが悪化しました。うまく書けているかもよくわからず。うーん……。
良さそうな部分だけを取り出してきて自分のコードと入れ替えてみてもうまくいかないのだなあと思います。
10.キックする
局所解回避のため、違反していない都市もランダムに1個「キック」する手法を試しました。
seed19ではスコア125176が出ましたが、スコアが悪化しているテストケースもありました。
11.おわりに
L=3の場合はコンテスト中の自分のスコアのほうが良かったため、組み合わせて提出する案も考えましたが、面倒になってやめました。
というわけで、今回の復習はここで一旦終了して、また次に必要となったときに、改めて勉強しようと思います。
最後はまとまりがなくなってしまいましたが、
それなりに推定できたぞー！
ということで終わりにしたいと思います。
興味を持った方は、ぜひ自分でもチャレンジしてみてくださいね！
（できるだけ正しいことを書きたいと思いましたが、いろいろと間違っているのではないかと思います。あと、正しくやれば自分は失敗したものでスコアが上がると思われます。詳しくは自分で調べていただければと思います。）
