この記事は？

AHC045の参加記です。
プレテスト39.5Gで、78位でした（2142 perf）

本番解法（78位）

概要

占いを使って座標推定する
1. 占いを使って辺の大小関係のDAGを作る
  1. 不確定度が高い400頂点について距離が近いL個の座標を占う
2. 全ての2辺について違反を減らすように辺を伸ばしたり縮める（450ms）
初期解を構築する
1. (0,0)から最遠点サンプリングでM個の代表頂点を決める
2. 代表頂点に近い頂点の個数を数えて、各代表頂点の木のサイズを決める
3. 各代表頂点までの距離をコストとし、最小費用流でMグループに分ける
4. グループ、ユークリッド距離、1で作ったDAGをもとにクラスカル法でMグループのMSTを並行して作る
解をローカルサーチで改善する（余った時間。600msくらい）
1. 山登り
  1. 近傍１：サイズが等しいサブグラフをswap
  2. 近傍２：移動してもサイズ制約を満たすサブグラフを移動
  3. 近傍３：2つのグループをマージし、グループサイズの制約を満たすよう分割
2. 最後に2.4のMSTをやり直して仕上げる

①占いを使った座標推定

占いを使って辺の大小関係のDAGを作る

頂点集合 $\{1, 2, 3, 4, 5\}$ を占い、辺集合$\{(1,2),(1,5),(2,3),(2,4)\}$が得られたとします。上の画像のようなMST（最小全域木）です。
この時、辺$(a,b)$のユークリッド距離を$\text{dist}(a,b)$と表すことにすると

$\text{dist}(2,4) < \text{dist}(3,4)$
$\text{dist}(2,3) < \text{dist}(3,4)$
$\text{dist}(2,4) < \text{dist}(1,4)$
$\text{dist}(1,2) < \text{dist}(1,4)$
$\text{dist}(1,2) < \text{dist}(1,3)$
$\text{dist}(2,3) < \text{dist}(1,3)$
$\text{dist}(2,3) < \text{dist}(3,5)$
$\text{dist}(1,2) < \text{dist}(3,5)$
$\text{dist}(1,5) < \text{dist}(3,5)$
$\text{dist}(1,2) < \text{dist}(2,5)$
$\text{dist}(1,5) < \text{dist}(2,5)$
$\text{dist}(2,4) < \text{dist}(4,5)$
$\text{dist}(1,2) < \text{dist}(4,5)$
$\text{dist}(1,5) < \text{dist}(4,5)$

が得られます。
つまり、「選ばれなかった辺は、その辺を足した時にできる閉路に含まれるどの辺よりも長い」という情報が得られます。
これはクラスカル法などの最小全域木を構築する貪欲アルゴリズムの正当性証明に出てくる議論です。

また、$\text{dist}(a,b) < \text{dist}(c,d)$と$\text{dist}(c,b) < \text{dist}(e,f)$が得られた場合、$\text{dist}(a,b)< \text{dist}(e,f)$も情報として扱いたい気持ちになります。
そこで、辺（2頂点のペア）を頂点として、得られた大小関係を辺とするグラフを作ると、大小関係には推移律が成り立つので、DAGができます。
※正確には、同じ距離がある場合にDAGにならないことがありますが、強連結成分分解すればよいです。

占いクエリについて

取りうる座標面積の降順で頂点を1つ選ぶ
その頂点から距離が近いL個の頂点を選ぶ

を400回繰り返しています（単にこれをやると割と全く同じクエリになるので、重複除去はします）

最上位勢はより賢い方法でクエリを作っているようですが、簡単なルールの中ではいろいろ試した結果これが1番良かったのでこれにしています。
気持ちとしては、MSTを作る時に不確定度が高い頂点をどの辺で採用するかが得られやすい点が嬉しいのかなと思います。

全ての2辺について違反を減らすように辺を伸ばしたり縮める（450ms）

占いで得たDAGを全始点DFSして、「今の推定座標（初期値は長方形の中心）のユークリッド距離では$\text{dist}(a,b) > \text{dist}(c,d)$なのに、占いの結果得られたDAG上では$\text{dist}(a,b) < \text{dist}(c,d)$になっている」2つの辺を探します。
占いが正なので、辺$(a,b)$を縮め、辺$(c,d)$を伸ばすように頂点a,b,c,dの座標をずらします。
ずらす量は、占い結果との違反長と、各頂点の取り得る面積の比で決めます。

常に2つの辺の制約だけで決めるので、「ある処理では頂点aを左下方向に移動するけど、ある処理では頂点aを右下方向に移動する」場合は、頂点aは左右に往復しながら下方向に向かいます。まぁ時間が十分あればその辺りは上手くいきます。
頂点に掛かる全体のペナルティを見ながら焼きなますか、バネを使ったグラフ描画アルゴリズムを持ち出すとより良いのかなと思いましたが、今の手法でも占いとの矛盾は95%くらい解消されるので、実装難度と実行時間の兼ね合いで採用しませんでした。
なお、真の座標と推定座標の誤差は18%くらい解消されます。減ってますが、劇的ではないですね。このことからも「占いとの矛盾を100%解消することに力を入れても、クエリ自体を大幅改良しない限り大差ないだろう」ということが分かりました。
（真の座標は、ローカルテスターに手を加えて標準入力に渡すようにしています）

②初期解を構築する

最小費用流で、厳密な容量制約がある時のクラスタリングを解きます。

Source->頂点
- 容量 = 1
- コスト = 0
頂点->グループ
- 容量 = 1
- コスト = ある頂点をそのグループに割り振った時のコスト
グループ->Target
- 容量 = グループのサイズ
- コスト = 0

です。
「グループのサイズ」は、入力として与えられたM個の木のサイズです。「ある頂点をそのグループに割り振った時のコスト」は、「そのグループの代表頂点までのユークリッド距離」とします。

従って、

どのM個の頂点を代表頂点とするか
各代表頂点は、どのサイズの木を担当するか
を決めればよいです。
前者については、最初を(0,0)として、「今の代表頂点集合から最も遠い頂点を代表頂点集合に加える」を繰り返しました。最遠点サンプリング（Farthest Point Sampling）というらしいです。
後者については、800頂点について一番近いグループを求めて、近い頂点が多いグループほど大きな木を担当することにしました。

フローを流したあと

これでグループ分けが求まるので、あとはグループ外と繋がないようにクラスカル法をすればよいです。
この時、DAGの逆辺も持っておいて、「逆辺がないものだけを採用候補とする（クラスカル法が進むごとに、採用済みの辺への逆辺は削除する）」と①で解消しきれなかった辺長違反を回避できます。

方針について

全体のMSTから、辺の長い順に削除してグループ分けする
プリム法やクラスカル法ベースで、全体のグループサイズの制約を見ながら構築していく
先にグループ分けして、グループ内でMSTする

この3方針があるかなと思っていました。
1は制約を満たすグループ分けが難しいと思っていましたが、実際は最上位勢はこの方針が多かったみたいです。
2は中途半端に余った頂点を遠くから取りに行かないといけないケースで弱いと思っていました。
3の中では自分の方針はかなり上手い方針なのではとコンテスト中は思っていましたが、あまり他に言及している人がいないので、単に賢いアルゴリズムを良い方針と錯覚しただけかもしれません。

TERRYさんは実装した結果棄却していました。

参考として、W=0、seed 0-99の100ケース平均は、この初期解の時点で182,281でした（③のローカルサーチを含めると164,788）。
1ページ勢はこの指標で15万を切っていて、これだけで10%くらい差が付いているみたいです。

解をローカルサーチで改善する（余った時間。600msくらい）

山登りをしました（近傍評価に対して時間が短く、焼くよりも山登りの方が良かったので）

近傍１：サイズが等しいサブグラフをswap

赤い3頂点の部分木をswap可能です。

近傍２：移動してもサイズ制約を満たすサブグラフを移動

サイズ5の木からサイズ4の木にサイズ1の部分木を移動しても、グループの制約は崩れません。

近傍３：2つのグループをマージし、グループサイズの制約を満たすよう分割

2つのグループをマージしてからサイズ4の部分木を切り離しても、グループの制約は崩れません。

最後にMSTをやり直して仕上げる

山登り中は辺長違反を気にせずにユークリッド距離でswapしている
グループ内がMSTになっているとは限らない
ので、②と同様に占い結果を使ったMSTで仕上げます。

おわり