とこはるのまとめ

多分考えたことがまとまっているはずです。きっと。おそらく。

Code Festival 2017 J (Tree MST) と 距離空間上のボロノイ図

春ですね。今回はCode Festival 2017のJ問題に対する面白い着眼点を紹介します。

問題はこちら -> J: Tree MST - CODE FESTIVAL 2017 Final | AtCoder 1900点!

ボロノイ図の説明はこちら -> ボロノイ図 - Wikipedia

想定読者層 :

  • MSTを知っている人
  • Kruskal法の適用中、頂点x,yを結ぶ辺が飛んで来たあと、それをMSTの辺として選んでも選ばなくてもその時点で構成中のMSTの辺のみを利用してxからyへ到達可能である、ということを理解している人

二次元空間上に点を配置した時の最小全域木(MST)のコスト

さて突然ですが、このサブタイトルの問題はどう解けるでしょうか。
やはり点の個数Nに対してO(N log N)程度で解けてほしい気持ちがありますが、
各点対間の距離を計算してしまうようではO(N^2)かかってしまいます。


いきなりですが、この問題の答えを言ってしまうと、

  1. ボロノイ図を構成する
  2. ボロノイ図で隣り合っている領域(点でなく、辺で隣り合う)に対して、それぞれに対応する頂点間の距離を計算する
  3. 計算した点対間のみの情報を利用してMSTを解くアルゴリズムに放り込む

です。

つまり、下図の例ですと、全部で6組の点対のうち、左側の点と右側の点を結ぶ点対は領域が接していないため計算する必要がないということです。
f:id:tokoharu-sakura:20180401021903p:plain


二次元ユークリッド空間上でボロノイ図を構成するO(N log N)のアルゴリズムが存在することが知られていて(参考 : Fortune's algorithm - Wikipedia)、さらに、(こういうアルゴリズムが存在するなら当然)隣接する領域の組の個数はO(N)であることが知られている(参考 : ボロノイ図とその3つの性質 | 高校数学の美しい物語 )ため、 このMST問題はO(N log N)で計算できることになります。

やはりポイントとなるのは「ボロノイ図で隣り合っているところしか見なくてよい」というところに尽きます。なぜこうなるのかをざっくり下図を用いてスケッチします。
f:id:tokoharu-sakura:20180331223807p:plain

これから、d(x,y)でx,y間の距離を表すことにします。

上図では、点x,y をおき、その中点をa、 さらに点zをd(x,a) = d(y,a) > d(a,z)となるようにとっています。
ボロノイ図で領域が隣接していない点対x,yをとった場合、このようなa,zがとれます(厳密にはとれない場合もありますが、それは細かいので考えないことにします)。

d(x,a) > d(a,z)の両辺にd(x,a)を加えれば、
d(x,y) = 2 d(x,a) > d(x,a) + d(a,z) >= d(x,z) がわかります。
これはd(x,y)と d(y,z)の関係に対しても言えます。

すると、Kruskal法では点対(x,y)より点対(x,z), (y,z)のほうが先に評価されることがわかります。
こうなると、点対(x,y)を比較するころには(x,z), (z,y)が先に連結になっていることから(x,y) の間もすでに連結だとわかるので、Kruskal法でこの点対(x,y)は必ず棄却されることになります。
したがって、点対(x,y)の距離の情報d(x,y)がなくてもアルゴリズムの返す解に影響はありません。

このような気持ちで、ボロノイ図を用いたアルゴリズムを構築することが可能です。

2次元空間からグラフの空間へ

次の問題を考えましょう。

距離付きのグラフG=(V,E,w)とVの部分集合Uを用意します。
集合Uに含まれる2点x,yの距離d(x,y)をグラフG上でx,yを結ぶ最短距離とします。
頂点集合としてUを持つ完全グラフH=(U,E',d)におけるMSTの最小コストはいくつか?
(つまり、xyを結ぶ辺のコストをd(x,y) とするときのMSTを求める問題です )

この問題は、距離を定義する空間を2次元のユークリッド空間から指定したグラフGから作られる空間にしたとみなせます(言い回しが数学的には雑ですが勘弁してください)。

では、この問題にも先ほど紹介したボロノイ図を用いた解法を用いることはできるでしょうか?

答えはYesです。上で用いたボロノイ図の説明をそのまま使う方針で説明可能で、その際「中点」など、ユークリッド空間特有の表現を距離空間上の言葉に直せば適用できます。

この説明で網羅していないのはスターグラフのようなケースで、要するにある頂点が多くの領域の境目になっているケースです。
そうなると、それぞれの境目について点対の距離を計算したいため、頂点数の二乗個の辺をアルゴリズムに突っ込みたくなります。
しかし、このケースでも、任意の点対が同じ距離なだけなので、Kruskal法を実行する際には順番を気にしなくてよいです。
したがって、代表点とその他の点を結ぶ辺のみをアルゴリズムに放り込めばよいことがわかります。

以上の考察から、次のアルゴリズムを得ることができます。
(ただ、言葉だけだとなんとなくわかりづらいので、この問題はボロノイ図っぽくやって境目を見つけれてMST、でOKだと思って飛ばして問題ありません。実際次節に図があるので、それだとイメージをしやすいかと思います。)

  1. プライオリティーキューに、Uに含まれる頂点と距離0の情報を挿入します。このキューの順序は距離で付けます。
  2. キューが空でない限り下のことをします
    1. キューから距離が一番小さい頂点vを選んで、キューからpopします。
    2. 頂点vに対して、まだ以下の説明にある隣接頂点を見ていく処理をしていないなら、その距離とU上のどの頂点から来たかを記録し、以下のように隣接頂点を見ます。
    3. 隣接頂点uを見て、これがすでに記録されているなら、頂点uに登録されている頂点と頂点vに登録している頂点の距離を、(uに記録された距離) + (vに記録された距離) + 辺v,uの距離として、Kruskal法で使うコスト情報として登録します。
    4. 隣接頂点uが記録されていないなら、これをプライオリティーキューに挿入します。このとき、vに記録した距離に(v,u)の距離を足したものであること、Uのうちどの頂点から来たかを伝えます。
  3. Kruskal法を動かす

このアルゴリズムはグラフGの頂点数Nと辺数Mに対して、だいたいO( ( N+M) log (N+M))程度で動作し、Kruskal法のために登録する辺数もM程度で抑えられるので、頂点集合Uのサイズが膨大でも動作します。

Code Festival J, Tree MST

本題に戻ります。しかし、ここまでの説明を読めば、この問題はかなり簡単ではないでしょうか。
というのも、TreeMSTで定義されている距離をグラフを用いて書いてみると以下のようになります。(この図は本家問題文の例1に対応しています)

前節の説明で頂点集合Uに相当するのが、1,2,3,4と黒字で番号がついている頂点の集合で、Vは1',2',3',4'を加えた8頂点からなる集合になります。
f:id:tokoharu-sakura:20180401000115p:plain

このようなグラフの作り方で、「頂点 u から頂点 v までの距離」と「Xu+Xv」の和、という距離をグラフで自然に表現できます。

これにボロノイ図的な考え方を適用すると次の色分けができます。
f:id:tokoharu-sakura:20180401002901p:plain

これで全域木に登録される辺の候補は、領域の境目となっている(1,2), (1,3), (1,4) でよいことがわかるので、コストは(1+1+3) + (1+1+2+5) + (1+1+2+3+1) = 22になることがわかります。

( UPD 19/1/14 補足・この上の色分けの図の直感的な説明は kobaeさんの説明
KEYENCE Programming Contest 2019 E - Connecting Cities - koba-e964の日記がわかりやすいです:

  • 頂点1, ..., Nから色1, ..., Nの液体が同じ速さで流れ始める
  • 色の違う液体は触れると触れた場所がその場で固まり、互いに混じり合わない。触れた場所以外はそのまま流れ続ける。
  • 最終的に全ての液体の動きが止まった時の液体の配置がヴォロノイ図である

そもそもボロノイ図はその定義から、以下動画のように、
各頂点からこのように色を広げていって、最終的にできる図形である、ということになります。
www.youtube.com
www.youtube.com

これと同様のことをグラフでやろうとすると、最初は頂点集合Uに含まれる頂点に異なる色を塗り、
それ以外の頂点が何色で塗られることになるのか調べることになります。
その結果、上の色分けになります。
また、これを行うために、ダイクストラ法のような実装になります。
)

このように、ちょっとオーバーキル気味ですが、ボロノイ図的な方針で解くことができます。
コードは Submission #1818510 - CODE FESTIVAL 2017 Final | AtCoder ここにあります。短いですね。(なお、とくにこの問題では領域の境目の個数がちょうどN-1個になりますので、Kruskal法を使う必要はありません。)

また、この着眼点から考えると、TreeMSTの元となるグラフを木でなく、一般のグラフに拡張しても自然に解けることがわかる点も面白いです。

類題

(UPD 19/1/14 ) KEYENCE Programming Contest 2019 E - Connecting Cities

Tree MSTの部分問題です。

snukeさん紹介の問題

自然にこれも解けますね(Judgeがどこにあるかわかりませんが)。

JOI 春合宿 2014 Day2 水筒

(HIRさんに教えていただきました。ありがとうございます!)
目標は違いますが、アイデアはよく似ています。
JOI 2013/2014 春季トレーニング合宿 課題

この方針が適用できない問題

今回紹介したボロノイ図的な考え方は、ある距離行列が与えられたとき、これを適切なグラフに埋め込んで表現できる場合に適用可能です。
したがって、次のような問題には適していないと思います。https://csacademy.com/contest/round-72/task/rectangle-mst/

この場合はこの距離行列を特定のグラフに埋め込むことができそうにありません.....

まとめ・感想

変なMSTが解けるテクとしてそこそこの汎用性がある気がします。

それにしても、計算幾何のアイデアをグラフに持ってきて解けるというところが非常に面白いです。ほかの計算幾何のアイデアもグラフに持ってこれないか、といった方向で問題を考案することもできるかもしれません。