2点間の距離（1辺の長さを1とする）が偶数なら頂点上、奇数なら辺上となる。
木の2点間距離と言えば、LCAを使ったアルゴリズムがある。
根を適当に決めて、各頂点の深さ（根からの距離）dep[v] を求めておく
c,d のLCAを lc,d とすると、c,d の距離は dep[c]+dep[d]−2dep[lc,d]
とはいえ、LCAを求めるアルゴリズムは典型ではあるがそれなりにややこしい。
今回の場合、距離そのものではなく、その偶奇がわかれば十分である。
LCAの項は2倍して使われるので、距離の偶奇は dep[c]+dep[d] の偶奇と一致する。
なので、LCAは求めなくても、dep を求めておくだけで、クエリには高速に答えられる。
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
n, qn = map(int, input().split())
links = [set() for _ in range(n)]
for _ in range(n - 1):
a, b = map(int, input().split())
a -= 1
b -= 1
links[a].add(b)
links[b].add(a)
depth = [-1] * n
depth[0] = 0
q = [0]
while q:
v = q.pop()
for u in links[v]:
if depth[u] != -1:
continue
depth[u] = depth[v] + 1
q.append(u)
for _ in range(qn):
c, d = map(int, input().split())
c -= 1
d -= 1
if (depth[c] + depth[d]) % 2 == 0:
print('Town')
else:
print('Road')
|
しりとりは有向グラフに置き換えられるので、まずグラフを作る。
ただしその際、単語を頂点として繋げてしまうと、
「105 個は“abc”で終わる」「105 個は“abc”で始まる」ような入力で、辺が 1010 本できてしまいTLE。
[aaaabc] → [abcxxx]
×
[bbbabc] → [abcyyy]
×
[cccabc] → [abczzz]
以下のように、頂点は先頭や末尾の「3文字」を表し、単語は辺にすると最大 2×105 本で済むようになる。
(aaa) (xxx)
↘ ↗
(bbb)→(abc)→(yyy)
↗ ↘
(ccc) (zzz)
その際、多重辺が生じうる点に注意する必要があるが、この問題では1本にまとめてしまってよい。
これに従ってグラフ化すると、ループしてる頂点グループや、行き止まりの頂点があったりする。
（図では3文字で無く1文字で表現する）
(a) → (b) → (c) → (d)
↑ ↓ ↓
(e) ← (f) (g) → (h)
↓ ↑
(i) → (j)
その3文字で終わる単語を言えば必ず勝てると判明した頂点を「必勝頂点」、
必ず負けると判明した単語を「必敗頂点」ということにする。
行き止まりはわかりやすく、必勝頂点である。
(a) → (b) → (c) → 勝(d)
↑ ↓ ↓
(e) ← (f) (g) → 勝(h)
↓ ↑
(i) → (j)
プレイヤーは、必勝頂点に遷移できる状態で相手にターンを渡すと、必ずそれを言われてしまう。
従って、必勝頂点に遷移できる直前の頂点は必敗頂点になる。
(a) → (b) → 負(c) → 勝(d)
↑ ↓ ↓
(e) ← (f) 負(g) → 勝(h)
↓ ↑
(i) ─→ (j)
次に、必敗頂点にしか遷移できない頂点は、
その状態で相手にターンを回せば必ず必敗頂点に遷移してくれるので、必勝頂点である。
(a) → (b) → 負(c) → 勝(d)
↑ ↓ ↓
(e) ← (f) 負(g) → 勝(h)
↓ ↑
(i) → 勝(j)
これを繰り返す。
(a) → (b) → 負(c) → 勝(d)
↑ ↓ ↓
(e) ← (f) 負(g) → 勝(h)
↓ ↑
負(i) → 勝(j)
すると、どうしても決まらない頂点群が残る（注: ループならば残るわけでもない）。
必勝とも必敗とも確定しない頂点に移動し続けることができる、ということなので、
これらは「永遠に続く」頂点となる。
実装の上では、逆トポロジカルソートのようにすればよい。
準備
Rv={r1,r2,...}: v に流入できる頂点リスト（逆辺）
ov: v から出る辺の数
ansv: 確定した必勝・必敗情報。最初は未確定で初期化
最初は、ov=0 の頂点が行き止まりなので、それを必勝頂点にしてスタックに積む。
その後スタックが空になるまで、
スタックから取り出した頂点を v とする
v への流入頂点 Rv={r1,r2,...} のそれぞれについて、
ことを繰り返すとよい。最終的に未確定なら、それは永遠に続く頂点となる。
Python3
なんか、単語を頂点のまま残し、3文字を表す頂点と混在させる変な実装をしてしまっている。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
n = int(input())
letters3_dict = {}
links = [set() for _ in range(3 * n)]
rev_links = [set() for _ in range(3 * n)]
out_degrees = [0] * (3 * n)
for i in range(n):
s = input()
prefix = s[:3]
if prefix in letters3_dict:
pi = letters3_dict[prefix]
else:
letters3_dict[prefix] = pi = len(letters3_dict) + n
links[pi].add(i)
rev_links[i].add(pi)
out_degrees[pi] += 1
suffix = s[-3:]
if suffix in letters3_dict:
si = letters3_dict[suffix]
else:
letters3_dict[suffix] = si = len(letters3_dict) + n
links[i].add(si)
rev_links[si].add(i)
out_degrees[i] += 1
m = len(letters3_dict)
links = links[:n + m]
rev_links = rev_links[:n + m]
out_degrees = out_degrees[:n + m]
ans = [-1] * (n + m)
q = []
for i, c in enumerate(out_degrees):
if c == 0:
q.append(i)
ans[i] = 1
while q:
v = q.pop()
if v < n:
for u in rev_links[v]:
if ans[u] != -1:
continue
if ans[v] == 1:
ans[u] = 0
q.append(u)
else:
out_degrees[u] -= 1
if out_degrees[u] == 0:
ans[u] = 1
q.append(u)
continue
win = ans[v]
for u in rev_links[v]:
out_degrees[u] -= 1
ans[u] = win
q.append(u)
for a in ans[:n]:
print(['Aoki', 'Takahashi', 'Draw'][a])
|