AHC045の参加記です。
プレテスト39.5Gで、76位でした（推定2151 perf）
頂点集合 $\{1, 2, 3, 4, 5\}$ を占い、辺集合$\{(1,2),(1,5),(2,3),(2,4)\}$が得られたとします。上の画像のようなMST（最小全域木）です。
この時、辺$(a,b)$のユークリッド距離を$\text{dist}(a,b)$と表すことにすると
が得られます。
つまり、「選ばれなかった辺は、その辺を足した時にできる閉路に含まれるどの辺よりも長い」という情報が得られます。
これはクラスカル法などの最小全域木を構築する貪欲アルゴリズムの正当性証明に出てくる議論です。
また、$\text{dist}(a,b)
そこで、辺（2頂点のペア）を頂点として、得られた大小関係を辺とするグラフを作ると、大小関係には推移律が成り立つので、DAGができます。
※正確には、同じ距離がある場合にDAGにならないことがありますが、強連結成分分解すればよいです。
を400回繰り返しています（単にこれをやると割と全く同じクエリになるので、重複除去はします）
最上位勢はより賢い方法でクエリを作っているようですが、簡単なルールの中ではいろいろ試した結果これが1番良かったのでこれにしています。
気持ちとしては、MSTを作る時に不確定度が高い頂点をどの辺で採用するかが得られやすい点が嬉しいのかなと思います。
占いで得たDAGを全始点DFSして、「今の推定座標（初期値は長方形の中心）のユークリッド距離では$\text{dist}(a,b) > \text{dist}(c,d)$なのに、占いの結果得られたDAG上では$\text{dist}(a,b)
占いが正なので、辺$(a,b)$を縮め、辺$(c,d)$を伸ばすように頂点a,b,c,dの座標をずらします。
ずらす量は、占い結果との違反長と、各頂点の取り得る面積の比で決めます。
常に2つの辺の制約だけで決めるので、「ある処理では頂点aを左下方向に移動するけど、ある処理では頂点aを右下方向に移動する」場合は、頂点aは左右に往復しながら下方向に向かいます。まぁ時間が十分あればその辺りは上手くいきます。
頂点に掛かる全体のペナルティを見ながら焼きなますか、バネを使ったグラフ描画アルゴリズムを持ち出すとより良いのかなと思いましたが、今の手法でも占いとの矛盾は95%くらい解消されるので、実装難度と実行時間の兼ね合いで採用しませんでした。
なお、真の座標と推定座標の誤差は18%くらい解消されます。減ってますが、劇的ではないですね。このことからも「占いとの矛盾を100%解消することに力を入れても、クエリ自体を大幅改良しない限り大差ないだろう」ということが分かりました。
（真の座標は、ローカルテスターに手を加えて標準入力に渡すようにしています）
最小費用流で、厳密な容量制約がある時のクラスタリングを解きます。
です。
「グループのサイズ」は、入力として与えられたM個の木のサイズです。「ある頂点をそのグループに割り振った時のコスト」は、「そのグループの代表頂点までのユークリッド距離」とします。
従って、
これでグループ分けが求まるので、あとはグループ外と繋がないようにクラスカル法をすればよいです。
この時、DAGの逆辺も持っておいて、「逆辺がないものだけを採用候補とする（クラスカル法が進むごとに、採用済みの辺への逆辺は削除する）」と①で解消しきれなかった辺長違反を回避できます。
この3方針があるかなと思っていました。
1は制約を満たすグループ分けが難しいと思っていましたが、実際は最上位勢はこの方針が多かったみたいです。
2は中途半端に余った頂点を遠くから取りに行かないといけないケースで弱いと思っていました。
3の中では自分の方針はかなり上手い方針なのではとコンテスト中は思っていましたが、あまり他に言及している人がいないので、単に賢いアルゴリズムを良い方針と錯覚しただけかもしれません。
TERRYさんは実装した結果棄却していました。
参考として、W=0、seed 0-99の100ケース平均は、この初期解の時点で182,281でした（③のローカルサーチを含めると164,788）。
1ページ勢はこの指標で15万を切っていて、これだけで10%くらい差が付いているみたいです。
山登りをしました（近傍評価に対して時間が短く、焼くよりも山登りの方が良かったので）
赤い3頂点の部分木をswap可能です。
サイズ5の木からサイズ4の木にサイズ1の部分木を移動しても、グループの制約は崩れません。
2つのグループをマージしてからサイズ4の部分木を切り離しても、グループの制約は崩れません。
一旦以上です。
システムテスト、各解説記事、解説放送を踏まえて感想とupsolveを追記予定です。
Be the first to comment
