読者です 読者をやめる 読者になる 読者になる

Union-Findを用いてそれぞれの木の大きさを高速で求める

問題

D: 道路の老朽化対策について - AtCoder Beginner Contest 040 | AtCoder

解法

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

Union-Findとは

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

keita-matsushita.hatenablog.com

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

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

解法ステップ

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

    1. その国民にとって通れる道路ならその道路によって年を結合(union)
    2. その国民の条件によって構築された木の大きさを保持
  5. それぞれの木の大きさを出力

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

入力値

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

その他の注意点

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

  • 独自の入力関数を定義
  • ループ内での出力を避ける

独自の入力関数を定義

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

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

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

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

ソースコード