けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 019 D - 高橋くんと木の直径 (水色)

木の直径の求め方を知っていれば解ける!!

問題概要

頂点数  N の木があるが、その形状についての情報はあらかじめわからない。あなたの目的は、この木の直径の長さを求めることである。

そのために、以下のクエリを 100 回まで投げることができる。

「2 頂点  u, v を指定して、パス  u- v の長さを聞く」

100 回以内のクエリによって、直径の長さを当ててほしい。

制約

  •  2 \le N \le 50

考えたこと

木が与えられたときに、木の直径は次の手順で求められることが知られている。

  • 適当な頂点  u を 1 つ選ぶ
  • 頂点  u から最も遠い頂点  v を求める
  • 頂点  v から最も遠い頂点  w を求める

このとき、パス  v- w が直径になるのだ。このことを知っていると、今回の問題はもう解けたも同然だ。


  1. なにか適当な頂点  u を選び、 u 以外の各頂点との距離を問いて、それが最大となる頂点  v を見つける ( N-1 回)
  2. 頂点  v から、それ以外の各頂点との距離を問いて、その最大値を求める ( N-1 回)

合計で  2N-2 回なので、制限回数以内に求められる。

コード

直径ライブラリは特に必要なかった。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, dist;
    cin >> N;

    int u = 0, vmx = -1, mx = 0;
    for (int v = 1; v < N; ++v) {
        cout << "? " << u+1 << " " << v+1 << endl;
        cin >> dist;
        if (mx < dist) {
            mx = dist;
            vmx = v;
        }
    }
    for (int w = 0; w < N; ++w) {
        if (w == vmx) continue;
        cout << "? " << vmx+1 << " " << w+1 << endl;
        cin >> dist;
        mx = max(mx, dist);
    }
    cout << "! " << mx << endl;
}