ebisukeプログラミング初心者脱出黙示録

30歳を過ぎてから始めたプログラミングと競プロの記録。Pythonで取り組んでいます。Arduinoで電子工作も

AtCoder-ABC209 D - Collision【Python解答例】

f:id:ebisuke33:20210711080110p:plain

AtCoder Beginner Contest209のD問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 209 - AtCoder



AtCoder Beginner Contest209 D - Collision

D - Collision

問題文

高橋王国は N 個の街と N−1 本の道路からなり、街には 1 から N の番号がついています。また、i(1≤i≤N−1) 本目の道路は街 ai と街 bi を双方向に結んでおり、どの街からどの街へもいくつかの道路を通ることで移動できます。道路は全て同じ長さです。

Q 個のクエリが与えられます。i(1≤i≤Q) 番目のクエリでは整数 ci,di が与えられるので、以下の問題を解いてください。

・現在高橋君は街 ci に、青木君は街 di にいる。二人が同時に街を出発し、それぞれ街 di, ci を目指して同じ速さで移動するとき、二人が街で出会うか道路上(両端の街を除く)で出会うかを判定せよ。ただし、二人とも最短経路で移動し、街の中を移動する時間は無視できるものとする。

制約

・2≤N≤10^5
・1≤Q≤10^5
・1≤ai

解答例

from collections import deque

inf = int(1e9)

n, q = map(int,input().split())

# 隣接リスト
road = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int,input().split())
    road[a-1].append(b-1)
    road[b-1].append(a-1)

C = []
D = []
for i in range(q):
    c, d = map(int,input().split())
    C.append(c-1)
    D.append(処理1)

# ある地点からの距離を記録するリスト
Dist = [inf for _ in range(n)]


# 1番(i = 0)の街から各街への距離を求めるBFS
def bfs():
    que = deque()
    que.append(0)
    Dist[0] = 0

    while len(que) != 0:
        p = que.popleft()
        for i in road[p]:
            if Dist[i] == inf:
                que.append(i)
                Dist[i] = Dist[p] + 1
    return


# Distを更新
bfs()

# クエリの処理
for i in range(q):
    tmp = (Dist[C[i]] - Dist[D[i]]) % 2
    # tmpの偶奇で出会う場所が決まる
    if tmp == 1:
        print("Road")
    else:
        print("Town")

解説

N個の街とN-1個の道があり、Q個のクエリが与えられます。
各クエリには高橋くんと青木くんがいる街が与えられ、ふたりが同時にお互いの街に向かって移動するとき、道で出会うか、街で出会うかを答える問題です。

移動速度や道の長さがすべて等しいので、お互いの街の距離が偶数のときは街で、奇数のときは道で出会うことがわかります。
したがってDistリストで街の距離を記録しました。

Distは街1(i = 0)をスタート地点としてBFSで各街への距離を更新します。

Distの処理が終わったら各クエリを処理しました。

CiとDiの距離の偶奇をtmpに記録し、奇数ならRoad、偶数ならTownと出力すればOKでした。




ABC209の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com