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

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

AtCoder Beginner Contest 070 D - Transit Tree Path

目次

結論

  • 題意を満たしながら,複雑な条件をシンプルに分割&個別に求めて,最後にまとめることができないか試す.

  • 最短距離を求めるときに,経路が決まっていなければダイクストラ法が,経路が決まっているときは幅優先探索が候補となる.

はじめに

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

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

想定読者

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

筆者の実力

  • AtCoderのレートで緑下位

記事の特徴

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

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

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


問題のリンク

D - Transit Tree Path (400点)

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

  • 最初の一歩は?

    • 簡単な図を書いて,愚直な解法を書き出す.

    •  Q個のクエリの答えを出力するよう要求されているため,1クエリあたりの計算が例えば O(N)だと計算量が O(NQ)となり,実行制限時間に間に合わない.

    • 前処理で,計算量を減らすことを考える.

  • 考察のキモ(Key Insight)は?

    • 題意を満たす経路は,同じ頂点を通る経路を考えない限り,各クエリとも1通りに決まる.

    • 「頂点 x_{j}から頂点 Kを経由して,頂点 y_{j}まで移動する」を2つの経路に分解する.

      • 「頂点 x_{j}から頂点 Kまで」の最短距離と「頂点 Kから頂点 y_{j}まで」の最短距離を求めることと等しい.
    • さらに,木は無向グラフであるため,向きによって2地点間の距離が変化しない.

      • この性質を利用すると,頂点 Kから任意の点 xまでの距離を求めればよいことになる.

      • 分解した後は,元に戻す.「頂点 x_{j}から頂点 Kまで」の最短距離と「頂点 Kから頂点 y_{j}まで」の最短距離の合計が求める答え.

    • 2点間の距離を求めるとき,幅優先探索を使う(計算量は,頂点の数V,辺の数をEとすると O(V + E)).ダイクストラ法を使うのは,経路が決まっていないとき.

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

    • 図を書いてみる.

    • グラフ理論,木の基本的な性質・特徴を学ぶ.

    • 経路を分けてみることができるか?

    • シンプルなアルゴリズムで回答できないか?

  • 実装のポイントは?

    • 幅優先探索

      • 各頂点の情報を隣接リストに格納する.隣接リストには,始点と終点をインデックスに指定して,値に頂点間の距離を入れる.

      • 初期化.

        • 頂点 Kからの距離が不明であることから,無限大で初期化.

        • キューを用意して,始点となる情報(今回は,頂点 K)を入れる.Python3の場合は,dequeを使用する.

        • ある頂点を見たかどうかをチェックするリストと頂点 Kから任意の頂点までの距離を格納するリストを用意する.

      • ある頂点から見たとき,隣接している頂点の情報を更新する.

        • 隣接している頂点を通っていなければ,距離を計算する.

        • キューに,この隣接している頂点の情報を追加する.

        • キューが空になるまで繰り返す.

    • 実行時間短縮のコツ

      • 入力を受け取るときにsys.stdin.readlinesを使う.

      • クエリ数の数だけ出力するときは,配列やリストに答えを格納しておいて,まとめて出力する.

Python3による回答例

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


def main():
    from collections import defaultdict
    from collections import deque
    import sys

    n = int(input())
    graph = [defaultdict(int) for _ in range(n)]

    # 入力の高速化のために使用.その分,消費メモリが増える.
    lines = sys.stdin.readlines()

    # 事前準備
    # 隣接リストに,頂点の座標を格納する.
    for i in range(n - 1):
        ai, bi, ci = map(int, lines[i].split())

        # 0-indexで処理するため,aiとbiは-1している.
        ai -= 1
        bi -= 1

        # インデックスに始点と終点を指定する.リストの値は,入力で与えられる頂点間の距離.
        graph[ai][bi] = ci
        graph[bi][ai] = ci

    q, k = map(int, lines[n - 1].split())
    k -= 1

    # 初期化:
    # 頂点Kから見たときの距離を無限大に設定.頂点Kの距離は0.
    dist = [float('inf') for _ in range(n)]
    dist[k] = 0

    # 次に見る頂点をキューに格納する.
    d = deque()
    d.append(k)

    # 頂点を見たかどうかTrue/Falseで管理する.
    visited = [False for _ in range(n)]

    # 幅優先探索
    while d:
        di = d.popleft()
        visited[di] = True

        for bi, ci in graph[di].items():
            # ある頂点を見たかどうかを判別.無限ループを回避している.
            if visited[bi]:
                continue

            # ある頂点における距離を求める.
            # 今回は,頂点Kから頂点diまでの距離(dist[di])と,頂点diから頂点biまでの距離ciの和で表される.
            dist[bi] = dist[di] + ci

            # 次に見る頂点をキューに追加.
            d.append(bi)

    ans = [0 for _ in range(q)]

    # Q個のクエリを処理
    for j in range(q):
        xi, yi = map(int, lines[n + j].split())
        xi -= 1
        yi -= 1

        # 頂点xiから頂点Kまで,頂点Kから頂点yiまでの距離を合計したものが答え.
        ans[j] = dist[xi] + dist[yi]

    # まとめて出力する.改行(\n)を入れている.
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

得られた知識・知見

  • 木には,ループが存在しない.2点間の距離は同じ頂点を通らない限り1通りに定まる.

  • 一見,複雑そうな条件を,分解&元に戻すことで題意を満たすことができないか,試す.

感想

  • 地点間の最短距離を求めるときに,ダイクストラ法を使うことにこだわりすぎていたようです.

  • 幅優先探索が,ようやく自分で書けるようになってきました.

参考

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

更新履歴

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