Skip to content

THIRDプログラミングコンテスト2025(AHC045)

問題概要

  • 平面上にN(=800)個の都市があり、各都市について、対応する長方形範囲(最大の幅・高さはW以下)内のどこかに存在することだけわかっている
  • クエリとして、Q(=400)回、以下の情報が得られる
    • 2個〜L個(=3〜15)都市を選ぶと、その都市集合で最小全域木を構成したときの辺情報(頂点番号順)が得られる
  • 最終的に、各都市をあらかじめ与えられるM個のグループ(各グループのサイズはG_i個)に分割し、各グループ内の都市は連結になるようにG_i-1本の道路を建設するような頂点・辺情報を出力せよ

時間

  • 240 時間

個人的メモ

クエリの使い方

  • 「クエリの結果をそのまま使って全域木を構築する」か、「現状の全域木の頂点の部分集合をクエリにして局所改善する」か、「推定に活用する」か、などいろいろ使い道がある
    • 方針によって、どこにどのぐらいクエリを使うか？などの調整もありえる

位置推定

  • クエリを使って各都市の位置をより正確にできるなら、その位置情報を使って全域木構築してもよい解が得られる
  • ぱっと見だとどこまで正確にできるかわからないが、最終的にはかなりよく推定できるため、推定を頑張る必要があった

バネモデルっぽい感じで調整

  • 「今の推定値で作ったMST」と「クエリの結果のMST」の辺の差分を見ると、今の推定値で作ったMSTの方だけにある辺はより長く、クエリの結果のMSTの方だけにある辺はより短い可能性がある
  • また、相対的に、おおよそ「クエリの結果のMSTに含まれる辺は相対的に短く、含まれない辺は相対的に長い」可能性がある
    • サイクルができるため含まれない場合は含まれなくても短い可能性がある
  • 辺の長さについて、もっと長そう、もっと短そう、という情報が使えるので、それを使ってバネモデルっぽく調整もできる
  • ただ、Lが小さい場合、簡単に調整できる一方、情報が少ないため、ズレが大きく、あまりよくなかった
    • 初期位置ランダムにして調整し直しを何回かやって平均取る、とか
  • wikipedia力学モデル (グラフ描画アルゴリズム)

不等式制約

  • 「クエリの結果のMST」に含まれる辺について、より正確に、辺の大小関係(不等式)の情報を取ることができる
  • 不等式の得方
    • ある頂点集合について、MSTとそれ以外の全域木を考えると、MSTは総長が最小になるので、「Σ(MSTの辺) <= Σ(全域木Tの辺)」になるので、共通する辺を両辺から除くと複数辺間の不等式が得られる
    • MSTの辺から1辺張り替えた全域木で考えると、「張替え前の辺の長さ <= 張替え後の辺の長さ」という不等式が得られる
      • MSTから1本取り除いて、連結になるように1本追加する、または、連結になる辺を全列挙
      • MSTに1本足すとサイクルができるので、そのサイクル上の辺を1本取り除く、または、サイクル上の辺を全列挙
  • 不等式を使って位置調整
    • 不等式をできるだけ満たすように、推定位置を微調整(長方形内ランダムに置く)する局所改善
      • 違反数、違反量(ReLUみたいなイメージ)を目的関数にして減らす方向に山登り・焼きなましで改善
    • 違反量の和を損失関数として考えると、各頂点について勾配を考えることができるので、勾配降下法で最適化
    • ギブスサンプリング(他の推定位置を固定してある頂点についてサンプリングし直す(長方形内から条件をできるだけ満たす点を選ぶ))
  • その他
    • 微調整とかで位置調整するとき、不等式条件の満たす満たさないの境界付近に収束しがちになってしまうので、マージン考慮やランダムにサンプリングなどを検討した方が良い
    • 凸じゃない(頂点位置が反転したようなのも解になったりする?)ようなので、局所解にハマる可能性があるみたい
      • 多点スタートやサンプリングを複数しなおしたり、ランダムウォークをいれたり、とか

クエリ設計

  • できるだけ近い頂点を選ぶ
    • MSTに必要なのは、基本的には「短い辺の情報」なので、ある頂点についてその近傍の頂点を選んでおくと、短い辺に関する情報が得られやすい
  • できるだけ分散が大きい頂点を選ぶ
  • できるだけ長さが同程度の辺を含むような(正三角形、正三角形の組み合わせに近くなるような)頂点を選ぶ
    • 「直線上に離れてならぶ3頂点」みたいにほぼ自明なものを投げてもあまり意味がない
    • 頂点が近くなくても、辺の長さが不確実性が高いものを選ぶと改善につながる情報が得られる可能性がある
    • Lが小さい(L=3)ケースなどでは重要そう
  • できるだけ重複しないように選ぶ
    • 選び方によっては同じ辺について何回も取得する可能性がある
  • できるだけ得られる情報が増えるように頂点を選ぶ
    • 現在の推定位置でのMSTより大きく異なるようなMSTになるクエリのほうが情報が増えて嬉しい
  • あえて推定しない点を決める
    • グループサイズが1のものがある場合、分散が大きい頂点に割り当てておくと、その頂点を無視できる

距離推定

  • MSTを構築するのに必要なのは「各頂点間の距離」(辺の大小関係)だけで、各頂点が正確に推定できている必要はない
  • 長方形が大きい頂点等の場合、ズレを過小評価する可能性があるので、長方形の大きさも考慮すると良い可能性がある
  • ギブスサンプリングなどで、「位置の期待値」を求めて距離を出すよりも、推定位置での距離を複数出して「距離の期待値」を求めるほうがよいっぽい

全域森構築

  • グループサイズ制約ありの全域森構築も長い辺がでないように構築するのは結構難しい

領域を荒く分割する/帯状に分けて考える

  • 基本的に、「長い辺」を使う場合にスコアが悪化するので、そのような辺ができないようにしたい
  • 領域を荒く分割して、その中の頂点か、隣接する区画の頂点だけと繋ぐように考えると、長い辺ができにくくなる
  • サンプルから3行程度変えるだけで実装でき、クエリを活用するとかなり改善する(解説放送)

TSP/1本道を作って順番にグループを割り当てる

  • TSPや1本道で1次元にすると、グループを順番に割り当てることができる
    • ユークリッドTSP(三角不等式が成り立つ、対称)を解く
      • ILSや焼きなましなど
    • TSPの辺をそのまま使うのではなく、割当後に頂点集合でMSTは構築し直すとより改善する
  • TSPなどだと総長を最小化しているため、グループに分割したときに良いグループ分けになっているわけではないが、割当を考えやすいのと、最終的な解に長い辺ができにくいので、結構良いスコアが出る
  • N=800と頂点数が結構多いのに対し、制限時間が最大でも2秒で結構厳しい
    • 収束しきれないかもなので、できるだけ無駄な遷移をしないようにしたり、初期解を貪欲解にしておく必要もあるかも
  • クリストフィードのアルゴリズム

全頂点MSTを切断して森を作る

  • 全頂点でMSTを作り、そのMSTの長い辺から順番に削除すると、Mグループを作ることができる
  • このとき、グループサイズの制約を満たすことも考えながら削除できる場合、最適な分割が得られる
    • その辺を削除したときの部分木サイズが、未割り当てのグループサイズのどれかになるなら削除できる
      • 部分和でもよい
    • 「1辺取り除くだけ」でなく、「2辺取り除いて連結になる1辺を追加」も考えられる
  • ただ、MSTの形状やグループサイズによっては割当ができない場合もあるので、探索の工夫や別途調整が必要っぽい
  • 最上位はこの方針が多かったっぽそう?

全域森を焼きなまし

  • 全域森を状態として、辺について「切断」「追加」「入れ替え」などを行うと局所改善ができる
    • 使える辺は限定したほうがよさそう？
  • この場合、辺の状態も考慮するため、グループについて最適でないような辺の状態も考えるため無駄があり、ある程度の変化になるまで手数が必要で、大きめの変更をさせにくい

頂点グループを焼きなまし

  • 頂点のグループ割当のみを状態として、局所改善を考えることができる
    • 実際の辺や総長は、グループの頂点からMSTを作る
  • 近傍
    • 部分破壊再構築(隣接2グループについてグループ割当をし直す、2つのグループの合計の頂点数と同じ別のグループがある場合にそれとswap)
      • prim法を1回実行し、残りを別グループとする
      • 2グループの全点でMSTを作ってグループサイズ制約を満たせる1辺取り除く
      • k-means
    • 頂点を移動させるパス(最短経路)を作って、パス上の頂点をスライドさせて移動
    • 2頂点swap
  • 評価関数
    • MSTを計算
      • Mが大きい場合などはグループサイズが小さいものが多いのであまり計算コストが掛からない
    • グループ内頂点間距離の合計/グループサイズ
    • グループの重心からの距離の和

木構造特定クエリ(木構造の局所改善にクエリを使う)

  • クエリの結果は真の座標で計算される正確なMSTになるので、そのまま解にすることも考えられる
    • 特に、長方形が大きい・位置推定が怪しいような頂点周り、など
  • グループの頂点の部分集合についてクエリを投げれば、その頂点集合でのMSTで正確なものが得られるので局所改善できる
  • グループサイズがL以下なら、そのグループのMSTは正確に作ることができる
    • また、複数グループをまとめて1クエリで投げることなども考えられる
      • グループが近いとグループ内で連結成分が分かれる可能性はありえそうなので、調整は必要そう

その他

Euclidean MST

Mが小さいケースでのMST計算

  • Mがある程度大きいケースが多いので気づきにくいが、最大で、M=1の場合、800頂点でのMSTを求めることになる
  • 制限時間ギリギリで調整したりしてこの構築時間を考慮していない場合は、手法によってはTLEになってしまったりする可能性があるので、要調整

使う辺を減らす

  • 遠すぎる辺を使わない
  • ドロネー三角形分割の辺のみを使う(Euclidean MST)

O(N^2)のprim法

  • 訪問済み頂点から未訪問頂点への最短距離を保持する配列を用意して、「最短のものを見つける→訪問済みに追加→配列を更新」を繰り返すとO(N^2)
  • ヒープやソートするやり方だと、使わない辺についても保持・計算するため若干遅いっぽい

W=0やL=∞やQ=∞の場合と比較する

  • 入力やテスターをいじって、頂点の位置が正確に分かる場合(W=0)や、クエリでまとめて頂点を投げられる場合(L=∞)、クエリ数を増やした場合(Q=∞)などと比較すると、推定精度や構築の伸び幅を確認できる
    • ビジュアライザからW=0のケースをまとめてダウンロードとかもできるので、それでスコアを見ると全域森構築パートの性能が比較できる

3点のMSTで条件を満たせる範囲

  • ある頂点a,b,cについて、cが存在しうる範囲は、MSTの結果から絞り込むことができる
    • aを中心に長さ|b-a|の円、bを中心に長さ|b-a|の円、辺abの中点を通る垂線、で領域を分けて考えると、MSTの結果によってそのどこかが絞られる

funcoder

解説

(50位まで&発言を見つけられた方のみ)