思考のジャンプ幅が狭いなら,飛ぶ回数で補えばいいじゃない!!

非情報系30歳が競技プログラミングやWeb開発を始めるとどうなるか?

AtCoder Beginner Contest 120 D - Decayed Bridges

目次

結論

  • 「ノードを結ぶリンクを一つずつ切り離す」を「ノードを結ぶリンクがない状態から,リンクを一つずつ付け加えていく」と言い換える.

  • 2つのノードが新たに連結されることで,行き来できるノードのペアが増加する.その増加分は,それぞれのノードとつながっている要素数の積で表される.

  • ノード同士がどのようにつながっているか? それがいくつあるのか? ということと,データ構造を工夫したアルゴリズムであるUnion Find木をどのように関連づけるか.

はじめに

  • AtCoderで出題された問題を復習しています.

  • 公式解説や上位陣による解説ブログを読んで,自分に足りなかった部分や得られた知見を消化してアウトプットしようと思います.

想定読者

  • 解説を読んで解き方はわかったものの,なぜその方法を思いつけるのか?と思った方.

筆者の実力

記事の特徴

  • なぜその発想に至ったのか,どうしたら解法を詰められるかといった点について,筆者なりの解釈をつづります.

  • 試行錯誤した過程から,得られた前提知識や着眼点を言語化していきます.

  • 間違いや勘違いなどがございましたら,ご指摘・ご指導いただけると幸いです(大歓迎です).


問題のリンク

D - Decayed Bridges (400点)

発想・解法とそれらを引きだすための方法・解釈

この問題の難しいところ

  • 「ノードを結ぶリンクを一つずつ切り離す」という操作を行うと,ノードの連結状態がどのように変化するのかが直感的に理解しにくくなる.

  • 愚直な解法だと確実にTLEするのは分かっていても,そこからどう計算量を減らしたらいいのか見当もつかない.

  • 前提条件として,Union Find木に関する知識(もしくは類する手法・知識)を知っている必要がある.かつ,解くべき問題とアルゴリズムの性質をうまく結びつけることが求められる.

考察のキモ(Key Insight)は?

  • 「ノードを結ぶリンクを一つずつ切り離す」を「ノードを結ぶリンクがない状態から,リンクを一つずつ付け加えていく」と言い換える.

  • 2つのノードが新たに連結されることで,行き来できるノードのペアが増加する.その増加分は,それぞれのノードとつながっている要素数の積で表される.

  • ノード同士がどのようにつながっているか? それがいくつあるのか? ということと,データ構造を工夫したアルゴリズムであるUnion Find木をどのように関連づけるか.

どうしたら思いつけそうか?

  • 問題文の操作そのものや操作の順番を逆にしてみる.

  • ペア数の増加量は,簡単なサンプルをシミュレーションして一般化する.

  • アルゴリズムの根本的な性質・特性を列挙して,解法の候補を絞っていく.

実装のポイントは?

  • あるノードを対象として,自分のいるグループの頂点数を調べる(筆者の場合だと,find_rootメソッド)ときに,根(最上位のノード)以外の場合は,その集合のサイズに-1を掛ける.

  • 2つのグループをつなぐときに,リンクを根から直接張り直す.これにより高速に計算できるようになる.

PythonによるAC解の一例

# -*- coding: utf-8 -*-


class UnionFind(object):

    def __init__(self, number_count: int):
        self.parent_numbers = [-1 for _ in range(number_count)]

    def find_root(self, number: int) -> int:
        if self.parent_numbers[number] < 0:
            return number

        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])
        return self.parent_numbers[number]

    def get_group_size(self, number: int) -> int:
        return -self.parent_numbers[self.find_root(number)]

    def is_same_group(self, number_x: int, number_y: int) -> bool:
        return self.find_root(number_x) == self.find_root(number_y)

    def merge_if_needs(self, number_x: int, number_y: int) -> bool:
        x = self.find_root(number_x)
        y = self.find_root(number_y)

        if x == y:
            return False

        if self.get_group_size(x) > self.get_group_size(y):
            self.parent_numbers[x] += self.parent_numbers[y]
            self.parent_numbers[y] = x
        else:
            # swap
            self.parent_numbers[y] += self.parent_numbers[x]
            self.parent_numbers[x] = y
        return True


def main():
    n, m = map(int, input().split())
    ab = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
    ans = [0 for _ in range(m)]
    ans[-1] = n * (n - 1) // 2
    uf = UnionFind(n)

    for i in range(m - 1, 0, -1):
        ans[i - 1] = ans[i]
        ai = ab[i][0]
        bi = ab[i][1]

        if not uf.is_same_group(ai, bi):
            ans[i - 1] -= uf.get_group_size(ai) * uf.get_group_size(bi)
            uf.merge_if_needs(ai, bi)

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

得られた知識・知見

  • Union Find木に関する基礎知識と実装方法を学んだ.あるグループのサイズや根を調べることができる.2つのグループが同じグループかどうかの判定,併合もできる.

  • 問題文の操作そのものや操作の順番を逆にしてみる.

  • ペア数の増加量は,簡単なサンプルをシミュレーションして一般化する.

  • アルゴリズムの根本的な性質・特性を列挙して,解法の候補を絞っていく.

感想

  • 脱初心者に向けて,典型力を高めたいと思える問題でした.

参考

記事を執筆された皆さまへ: 掲載不可の場合はお手数をお掛けしますが,@k_hiro1818までご一報ください.

更新履歴

  • 2019/06/29 作成
  • 2019/0x/xx 更新