AtCoder-ABC209 D - Collision【Python解答例】
AtCoder Beginner Contest209のD問題についてPythonの解答例を記事にしていきます。
AtCoder Beginner Contest 209 - AtCoder
AtCoder Beginner Contest209 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