概要

最近F - Construct HighwayやA - Reachable Townsが立て続けに解けなくて悲しかったので、お互いに共通する「UnionFindの各連結成分が変数を持っていて、mergeするときにその変数を使ってなんかする」みたいな問題をすっとかけるようにしたいなと思い、考え方を記すことにした。他にも使う問題があったら足していきたい/教えてほしい。

考え方

各連結成分が持つ変数のことを $x$ で表すことにする。両方の問題で言えることだが、

$x$ はどのような値なのか？
どの $x$ を持つ連結成分とマージするのか？
どうやってマージするのか？

を考える必要が出てくる。以下それぞれの問題に対して順番に考えていく。

1. $x$ はどのような値なのか？

ここがうまいこと設定できればこの解き方で解ける可能性が高そう。

F - Construct Highwayについてはその連結成分のうち、次数が足りない頂点群を $x$ とすればよい。（例えば、 $x = \{1,1,3,4\}$ ならその連結成分についてはまだ頂点1は2回、頂点3は1回、頂点4は1回別の連結成分とつなぐ必要があることを表す）

A - Reachable Townsについては、各連結成分が持つ点のy座標の最小値を $x$ とすればよい。

2. どの $x$ を持つ連結成分とマージするのか？

すべての連結成分をなめてその都度 $x$ を見ていると $O(N^2)$ かかり、TLEになってしまう。そこで、各 $x$ がうまく管理されるようにしといてやる必要がある。 $x$ を管理するために、各連結成分について代表点 $p$ を $x$ と結びつけておく。

二つの問題に共通していることだが、必要なのは $(x,p)$ というペアが適切にソートされていて、削除や追加、検索にそんなに時間を要さないこと。ということは、setを使えばうまくいきそうだということがわかる。従って、F - Construct Highwayについては、 $(x, p)$ というペアを $x$ の長さの降順にソートされるようにsetに入れておけばよさそうだし、A - Reachable Townsについては $(x, p)$ というペアをそのままsetに入れておけばよさそう(デフォでsetはless<int>()でsortするので)。

そうしたら、あとはsetの先頭と比較していけばよい。F - Construct Highwayなら先頭の二つをmergeしていけばいい。A - Reachable Townsなら $x$ が見ている点のy座標より小さいものについてずっとmergeを繰り返していく。

3. どうやってマージするのか？

ここまでくればもう後は自然に書けそう。ここの処理は当然問題によるが、一応書いておく。

F - Construct Highwayについて、 $(x_1, p_1)$ と $(x_2, p_2)$ がmergeされるときは、setから二つをpopしてきて、 $x_1$ と $x_2$ の末尾頂点をpop_backする。そのあと二つを融合させた $x_3$ がsizeが1以上なら $(x_3, \mathrm{parent} (p_1))$ をsetに再挿入。（なんか $x$ のサイズがでかいときにTLEしそうな感じもある？その場合setからコピー&popするんじゃなくてうまいこと参照とか使う必要があるかも、後でmergeしてから二つ目の要素をeraseする方法も試して、時間を比べてみる）

A - Reachable Townsについて、 $(x_1, p_1)$ と現在見ている頂点 $(x_2, p_2)$ （ただし $x_2$ は $p_2$ のy座標）がmergeされるときは、setから $(x_1, p_1)$ をpopしてきて $p_1$ と $p_2$ をmergeする。これを $x_1 \lt x_2$ となる $x_1$ について繰り返したのち、それらの中で最も小さいy座標を $x$ としたときに $(x, \mathrm{parent} (p_2))$ をsetに再挿入すればよい。