🗺️
AHC045振り返り

2025/04/10に公開
 はじめにAtCoder Heuristic Contest 045 の振り返り。今回は700位台でかなり悪いスコアしかだせなかった。

 問題問題はN個の都市をM個のグループに分けて、同じグループの都市間で道路を接続するという問題。グループはサイズが事前に与えられている。都市の位置が範囲でしか与えられていないので、正確な位置がわからないのが課題。

 サンプルを参考にしてみる問題と一緒にサンプルが用意してある。手順としては以下の通り。
都市の位置の中心でソートし、その順番で分割する
各グループについて、3都市を2都市ずつスライドしながら選択しクエリをだす。クエリの応答として得られた辺をそのまま回答に追加
各グループについて最後の都市を含むクエリができなかった場合は、グループ内の直前の都市との変を回答に追加する
始め、これで答えがでるのがよくわからなかった。都市の数Nが800、送信可能なクエリの数Qが400で固定なので、Nの半分つまり「2都市ずつ」スライドしながら (a_{2i}, a_{2i + 1}, a_{2i + 2}) を結ぶ道路を作っていけばグループ内を結ぶ木が、クエリ数Q以下で作成できる。

 都市をどのようにしてグループに分けるか
 空間充填曲線を使うサンプルでは都市の位置(x_i, y_i)でソートしている。tupleのソートは要素順に行うので、x_iでソートして、同値の場合はy_iでソートすることになるので、細長いグループばかりになってしまう。近い都市が近くになるようにソートして...というケースには空間充填曲線を使うのが良さそうである。ヒルベルト曲線の方が性能がいいのかもしれないが、今回は実装の簡単なz-order曲線を使ってみた。


z-order 曲線
z-order曲線とは、上図のようにZの形で空間を埋めていく曲線である。メリットとしてはx座標とy座標からの変換が用意なこと。図からもわかるように2進数表記で交互に組み合わせると変換できる。Pythonで書くと以下のような感じ。もっと綺麗に書けそうな気はする。
def zorder(self, x:int, y:int) -> int:
        result = 0
        i = 0
        while x != 0 or y != 0:
            result |= (x & 1) << i | (y & 1) << (i + 1)
            wx >>= 1
            wy >>= 1
            i += 2
        return result
デメリットとしては、zとzの間で不連続になってしまう事。上図でも7と8の間は不連続になってしまっている。
サンプルをそのままローカルツールで提供されている100個のサンプル入力値に対して適用した時のスコアの合計は178,407,088点だったが、z-order曲線でソートするように変更すると、41,837,746点と1/4以下に減少した。今回はスコアが小さい程よい。

 グループの順番を入れ替えるz-orderでソートした後、入力で与えられたグループの順番通りに都市を分割していたが、z-orderの欠点として挙げたように「zとzの間で不連続になってしまう」ので、同じグループにここの部分が入ると細長いグループができてしまう。そこで、グループの順番を入れ替えてみる。
グループの数Mは、1 \lt M \lt 400なので、総当たりだと400!になって計算できない。そこで山登り法で解いてみた。近接解は、M / 2以下離れた2つのグループを入れ替えることで求めた。入れ替えなかった前後のグループは変化しないので、「全部変わってしまう」のを避けることができる。また、できるだけグループの形を正方形にした方がいいと考えたので、各グループの長辺の長さを足し合わせてスコアとし、小さい値ほどよいとした。
これでスコアは 39,171,560点 (-2,666,186) となった。焼きなましも試すかな？とは思ったが、そこまでする必要はなさそうだったので、山登りのままとした。

 重ならないように調整する

グルーピングの結果 (ggplot2のggforceライブラリを用いて描画)
現在のグループの様子をプロットしてみると、領域が重なってしまっている。重なりが小さい方が距離としても短くなるはずなので、調整を行った。


都市の入れ替えによるグループの重なり回避
やり方としてはシンプルに、ランダムに2つグループを選択し、端っこの都市（上図だと左端と右端）の都市を入れ替えて、それぞれのグループの領域の面積の合計が減るか変わらなければ採用、増えたら不採用という山登り法的な進め方を実施した。2つのグループの選択は衝突を計算する...のが面倒だったので、z-order順に並んでいるのだから、近くにあるグループは位置的に近いだろうという大雑把な方法で行った。


重なりを軽減させた結果
狙い通り重なりが軽減されている...気がする...とりあえずスコアをだすと 46,618,677点（+7,447,117）...増えてしまった。この処理はキャンセルとした。

 グループ内の道路作成
 占いに頼らずに最小全域木を作るサンプルでは「占い」によって木を作成しているが、都市の座標を使えば「占い」と同じアルゴリズムで木を作ることができる。

当然正確な都市の位置ではないが、とりあえず試してみた。
スコアは 36,240,148点（-2,931,412）占いを行わなくとも精度が上がった。

 占い結果で木を修正する占いをどう使うか? について検討した
グループ内の都市がL個以下の場合、すべての都市で占い、その結果をそのままグループの木とする
グループないの都市がL個を超える場合、L個のサブツリーで占い、その結果を現在の木を置き換える。都市の数の半分回数これを繰り返す


占いによる都市間の道路の変更
2つ目は上図のような感じで、部分木だけでも正解を用いた方がいいのでは？というイメージ。
1だけだと34,033,351点、2も入れると33,414,441点 (-2,825,707)なので、狙い通りに効果がでている印象。

 都市の位置を推定するこれ以上精度を上げるには、都市の位置を正確に推定する必要があると考えた。理由としてはヴィジュアライザでみると、都市の推定位置（入力として与えられる領域の中心）では、それっぽい木ができているが、実際の位置での木を見るとぐちゃぐちゃだからである。


都市の存在される可能性のある中心地（左）と実際の位置（右）
位置の補正について、考えたが思いつかなかった。今回の占いでわかるのは最小全域木なので、他の辺よりも長い辺だけ。占いの結果と、今の座標から求める最小全域木が違う時に都市を動かせばいいのだと思うが、どうやればいいかの判断が難しい。

 都市の外から引っ張る

都市の領域外の都市から引く
こういうのはバネかなぁとも思ったが、都市間の長さは一定でもないし、その比もわからない。イメージとしてとあるターゲットの都市に対して、周りの都市から引っ張っていくイメージで、以下のような処理を行った。
都市が存在するとされる領域を大きい順に並べ、ターゲットとなる都市を決める
ターゲット都市の領域の右上, 右下, 左上, 左下に位置する一番近い都市を見つける
それら合計5つの都市を使って、ターゲットを必ず含む四角形を４つ作り占う
都市の間に道路がある場合都市間を短く、道路がない場合は長くなるように都市を動かす。この時以下のように決めた
その都市の領域に比例して動かす（領域が大きい都市ほど大きく動く）
現在の位置から求められる最小全域木と同じ解となる場合は動かす距離を1/10にする
最小全域木と占いの結果が等しくなれば終わりであるが、終わらないこともあるので、一定回試行したらあきらめる
最初よりも占いから外れた最小全域木ができた場合、巻き戻す



最初の誤差からの改善率
実行して、正しい都市の位置と推定した都市の位置の差分をプロットした結果が上の図の通り。横軸は処理時間になる。ターゲットの都市が増えていくので、段々誤差が小さくなる単調減少のグラフになることを期待していた。現実はパラメタの調整がかなり難しく、上下を繰り返している上に最後には、補正前より誤差が大きくなってしまっている。一番底の部分でも 0.08%しか改善していないので、かなり微妙と言わざるを得ない。

 まとめ他にも色々試してみたがよい結果はでず、結局都市の位置補正は出来ずに時間切れとなった。解説を読むと、近くの都市を集めてグルーピングしたり、最小流量制限付き最大流問題に落とし込んでいたりしていた。かなりの日数を都市の位置を推定することに費やしてしまったので、グルーピングの他の手法を試すことをしなかったのが敗因かもしれない。