[Python] ABC019 D

問題

D – 高橋くんと木の直径

回答

20点回答

全て探索します。

AtCoder Beginner Contest 019 解説 from AtCoder Inc.

import sys

N = int(input())

ans = 0
for i in range(N):
    for j in range(i+1, N):
        print ("? {0} {1}".format(i+1, j+1))
        sys.stdout.flush()
        dist = int(input())
        ans = max(ans, dist)

print('! ' + str(ans))

100点回答

AtCoder Beginner Contest 019 解説 from AtCoder Inc.

スライドでも十分わかりますが、以下がとてもわかりやすかったです。

木の直径を求める

また、double-sweep は英語ですが以下にあります。

Linear‐time graph distance and diameter approximation

import sys

N = int(input())

# 木の頂点から一番離れた頂点vを求める。
farthest_vertex = 0
max_distance = 0
for i in range(N):
    print("? {} {}".format(1,i+1))
    sys.stdout.flush()
    distance = int(input())
    if max_distance < distance:
        farthest_vertex = i + 1
        max_distance = distance

# vから最も離れた点までの距離が直径になる
ans = 0
for i in range(N):
    if farthest_vertex == i+1:
        continue
    print("? {} {}".format(farthest_vertex, i+1))
    sys.stdout.flush()
    distance = int(input())
    if ans < distance:
        ans = distance

print("! {}".format(ans))