問題

解法

Union-Findを用いて、それぞれの国民の持つ条件によって作成される木(都市と道路の関係図)の大きさ(都市数)を求める。

木が持つ情報(高さ、大きさ、どの要素を持つか)を状態別に管理することで、それらの情報を高速に求めるためのデータ構造。詳しくは以下の記事を参照

Union-Findの制約として、結合はできるが分割はできないというものがある。よって、国民が持つ「結合条件が厳しいもの」から操作する必要がある。この制約を考慮するために、国民と道路をそれぞれ「年」によってソートした状態でUnion-Findを構築していく。

これらを踏まえ、以下のステップで問題を解く事ができる。

国民を「年(それ以下の年に出来た道路は通行できない)」が最新順になるようにソート
道路を「年(道路が作成された年)」が最新順になるようにソート
Union-Find作成 (木の大きさをプロパティに保持)
ある国民に対して、各道路をチェック
1. その国民にとって通れる道路ならその道路によって年を結合(union)
2. その国民の条件によって構築された木の大きさを保持
それぞれの木の大きさを出力

例として、以下の入力値を考える。

入力値

するとUnion-Findによる操作は以下の流れとなる。この時、国民・道路はそれぞれ年が最新順にソートされ操作されている。

この問題は時間制限がかなり厳しく設定されている。よって、通常の実装に比べ以下の２点の改善が必要。

独自の入力関数を定義

Javaでは、値の入力にScannerを用いる事が一般的であるが、Scannerは処理スピードがとても遅い。その為独自で入力するためのクラスを定義し使用する必要がある。

ループ内での出力を避ける

Javaでは、値の主力にはSystem.out.println()を用いるが、この処理も遅い。よってStringBuilderを用いて出力する文字列を改行文字付きで形成しprintするのは１度のみにする。

これらの処理を行わないとテストが通らなかった。