なんとな~くしあわせ?の日記

「そしてそれゆえ、知識そのものが力である」 (Nam et ipsa scientia potestas est.) 〜 フランシス・ベーコン

AtCoder - AtCoder Beginner Contest 040 (道路の老朽化対策について) を解いてみた

ABC 040 D問題に使われるアルゴリズム要素はUnion-Findです。

Union-Find自体は前回ブログ記事にしていたのですが…これだけでは足りませんでした。ACするためには経路圧縮とrankによる木のマージ処理が必要です。

nantonaku-shiawase.hatenablog.com

今回の内容はAOJ本にバッチリ書かれています。

アルゴリズム

経路圧縮

前の記事の中で、ある要素の最上位の親を求める処理を以下のように求めたはずです。

def root(i, id)
  while i != id[i] do
    i = id[i]
  end
  i
end

しかし、これではある要素を求める際に毎回whileループが回ります。計算量が増えてしまいます。以下のようにすることで、途中までの要素を全て書き換えます。関数名はfind_setに変えます。

def find_set(i, id)
  if i != id[i]
    id[i] = find_set(id[i], id)
  end
  id[i]
end

rankによる木のマージ処理

木のマージ処理に関しては、擬似コードのほうがわかりやすいでしょう。前回作ったuniteという関数に以下のような処理を加えます。

またアメリカの大学の資料から

UNION-BY-SIZE (x, y) 
    r ← FIND (x).
    s ← FIND (y).
    IF (r = s) RETURN.
    ELSE IF (size(r) > size(s))
        parent(s) ← r.
        size(r) ← size(r) + size(s).
    ELSE
        parent(r) ← s.
        size(s) ← size(r) + size(s).

これらを行うことで計算量が削減され、満点となるようです。AtCoderの問題としては、これらの計算量の削減がなくてもロジックとUnion-FIndの実装ができていれば50点もらえます。

解答

  • 今回、解答の作成にあたってはだいぶ他の人の解答を真似している面があります…コピペはしてないけど

Submission #1754689 - AtCoder Beginner Contest 040 | AtCoder