Zenn
🔮

THIRD プログラミングコンテスト2025（AtCoder Heuristic Contest 045）参加記

に公開
競技プログラミング
idea

問題ページ

https://atcoder.jp/contests/ahc045/tasks/ahc045_a

提出した解

最終的な解法のビジュアライズは下記のようなものになりました(seed=1)。

コードはこちら。プレテスト17位、最終16位でした。プレテスト50ケースの絶対スコア： 9,030,604
https://atcoder.jp/contests/ahc045/submissions/64611091

解法

概要

質問により頂点間距離の大小関係が得られるので、その大小関係をもとに頂点位置を推定します。

  • 質問
    • クエリはお気持ち評価関数で評価する
    • 質問の途中に焼きなましで頂点位置の推定値を更新
  • 頂点位置の微調整
    • 嘘三分探索による調整
    • 大小関係のルールに違反しない領域のなるべく中央に寄せる
  • 森の構築
    • 破壊再構築焼きなまし

頂点間距離の大小関係ルール

ジャッジからの回答であるMSTの中で、MSTに含まれる辺 s-t を切断したとき連結成分が2個に分かれますが、その2個の連結成分をつなぐ辺としては辺s-tが最小であるはずです。
よって、s側の連結成分にある頂点uと、t側の連結成分にある頂点vに対して d(s,t) < d(u,v) という4頂点に関する大小関係ルールが得られます [1]。
ただし s!=u または t!=v であり、関数 d(a,b) は頂点a,b間のユークリッド距離です。

s=u であるときは d(s,t) < d(s,v) という3頂点に関する大小関係ルールになります。

質問をするたび、回答のMST内の各辺の切断を試し、そこから得られる大小関係ルールを全て保持しておきます。
例として、私の最終的な解では L=15のケースで400回質問した後に、約15万の大小関係ルールが得られていました。

クエリ作成

評価関数

お気持ち評価関数で頂点集合を選んで質問します。頂点集合は下のようなものが嬉しい気がします。

  1. 頂点が相互に近くにあれば、局所的に最適な木が得られるので最終的な出力にそのまま流用できそう

  2. 大小関係ルールをたくさん獲得するため、大小関係ルールが全くない頂点の組を多く含めたい。4つ組よりも3つ組のルールのほうが有用そう。

  • 1.について

これは、頂点集合にある全頂点ペア間の平均距離などで評価できそうです。ただし、絶対距離で評価すると、近くに頂点が存在しない孤立した頂点を全く質問しないという事態が発生するかもしれません。そこで、絶対距離ではなく距離のランキングの平均値を取ることにします。

distance_rank(u,v) = (uから見てvは何番目に近いか)

この distance_rank をクエリ内の全てのu,vペアについて求めて平均をとります。この平均値はなるべく小さいほうがいいです。

  • 2.について

これは、頂点集合にある全ての頂点3つ組でのルール数平均などにより評価できそうです。仮に頂点3つ組(u,v,w)に対して、 d(u,v) < d(v,w) < d(u,w) が成り立っているとしたら、大小関係ルールは最大3個まで獲得できます（推移律により2個で十分かもしれません）。
コンテスト中はそもそもルールが3個得られることに気づいていなかったので（？）、3つ組に関して何かしら1個でもルールがあるかどうかを評価しています。

hasrule(u,v,w) = (u,v,wの3頂点に関する大小関係を何か一つでも獲得しているなら 1、していないなら0)

この hasrule をクエリ内の全てのu,v,wの組について求めて平均をとります。この平均値はなるべく0に近いほうがいいです。

  • 最終的な評価関数

上記2個の平均を用いて、下のような感じで計算します。

(1.0 - avg(has_rule)) * exp(-α * avg(distance_rank))

頂点集合の選択

中心座標を無作為に選んで、そこから最も近いL個の頂点を選んだ頂点集合を、クエリ候補にします。
なるべく良いクエリにするため、上記の構築方法でクエリ候補を15個作り、評価値が最も高いクエリ候補をクエリとして選出します。

さらに、選出したクエリを、1点交換山登りにより評価値改善を行います。

そうして改善したクエリをようやく質問します。

質問途中の頂点位置調整

クエリの評価関数を計算するにあたり、頂点位置を仮に決めておく必要があります。
最初は各頂点を長方形の中心に仮決めしますが、質問により大小関係ルールがある程度溜まったら頂点位置の調整を行います。そうすることでクエリの評価関数の妥当性が改善されます。

位置調整は焼きなましにより行いました。
質問のたびに調整をするのは処理が重すぎるため、複数回質問をした後に調整を挟むことにします。提出コードでは、80回質問をするたび40msずつ焼きなまして頂点位置を調整しました。

焼きなまし

  • 評価関数

焼きなましの評価関数には、大小関係ルールの違反度合いを使います。
大小関係ルール d(s,t) < d(u,v) があるとき、s,t,u,vの頂点位置からコストを計算します。

cost(s,t,u,v) = max(0,d(s,t)-d(u,v))

ルールに整合している場合はコスト0になり、不整合の場合は距離の差分がコストになります。
全ての大小関係ルールからコストの総和を求めて、焼きなましの評価関数とします。

  • 遷移

焼きなましの遷移は非常に単純で、ランダムな頂点1個をランダムな方向にランダムな距離だけ移動させるだけです。頂点が長方形の外に出てしまったらやり直します。

なお、ランダムな距離だけ移動させる際、微小な移動も巨大な移動も発生するよう、移動距離に傾斜をかけます。実装では移動距離を 2^p （pは1～10の一様乱数）としました。

頂点位置の微調整

嘘三分探索

頂点位置推定が完璧に動作していれば、大小関係ルールの違反は0になるはずです（実験として、ジャッジが持つ正確な位置を入力すると確かに0になりました）。
しかし焼きなましで得た頂点位置はあまり良くないようで、ちょくちょく違反が発生しています。

別の方法で頂点位置を微調整することで推定精度改善を目指します。頂点aに関するコスト総和は下記のようになっているのですが、

Σ max(0,d(s,t)-d(u,v))
a ∈ {s,t,u,v}

このコスト総和は頂点aの位置に対して 単峰に近いと信じます 。根拠は直感です。

単峰であるなら三分探索で改善できるので、各頂点をx軸とy軸について交互に3分探索をすることで頂点位置を更新します。
実装してみるとコスト関数の値が減少したので、まあやって良かったということで。

嘘二分探索

ところで、違反無しにできる頂点は、違反が発生しない領域のうちどこに配置してもコスト0なので、適切な位置が分からない問題があります。直感的には、違反が発生しない領域の中央に置いておけばMST構築に大失敗しにくくなると期待できます。

ここで、違反が発生しない領域は 凸図形に近いと信じます。根拠はやはり直感です。

そこで、三分探索で求めた頂点位置を始点にして、違反が増加しない上下左右の幅を二分探索で判定します。
上下幅の中央・左右幅の中央に頂点位置を移動させることで、違反が発生しない領域の中央に近づけると期待します。

ただ、斜めに細長い楕円などではこの方法で中央へ到達するのは困難だと思うので、この方法はあまり良くないと思っています。
サンプリング的なことをするほうが筋が良さそうです。

以降、頂点間距離はここで決めた頂点位置を真として計算した値を用います。

森の構築

森は破壊再構築焼きなましで構築します。
適当にプリム法の繰り返しで初期解を構築した後に、木のサイズは常に正しい値を維持したまま変更を繰り返します。

  • 遷移1 近距離にある2個の木から1頂点ずつ選び、頂点を交換する

  • 遷移2 近距離にある2個の木にある辺を全て削除し、プリム法で再構築

遷移2について

サイズG1とG2の木を選んだとします。まず2個の木にある辺を全て削除し、頂点を無所属化させます。その後、無所属化された頂点のうち1個を無作為に選んで始点とし、プリム法でサイズG1のMSTを構築します。サイズG1の木に含まれなかった残りの頂点から同じくプリム法でMSTを構築することで、遷移が完了します。

脚注

  1. 厳密には等号が成り立つこともありますが気にしない ↩︎

Discussion