ABC019 D問題（高橋くんと木の直径）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）019 D問題をC++で解いてみました。ABC019は、2015年2月28日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

D問題 高橋くんと木の直径（Difficulty : 1378（参考値））

問題の詳細は、リンク先をご覧ください。

ABC019 D問題 高橋くんと木の直径

木の直径を求めるために、ある頂点から他の頂点への最短距離を2回計算します。AtCoder Problems による Difficulty は 1378（参考値）でした。

解答案

木の直径についてはすでに記事にしています。木の直径は、以下の手順で求めることができます。

• ある頂点 $a$ から、もっとも遠い頂点 $b$ を求める。
• その頂点 $b$ から、もっとも遠い頂点 $c$ を求める。
• 頂点 $b$ と頂点 $c$ の距離が木の直径となる。

C++ プログラム例（ABC019D）

インタラクティブな問題です。頂点の数 $N$ について、$2 \leqq N \leqq 50$ かつ頂点間の距離を最大100回まで問い合わせることができます。

• 頂点1から残りの頂点までの距離を問い合わせて、一番遠い頂点 dist1_index を求めます（9ー19行目）。最大49回問い合わせます。
• 頂点 dist1_index から一番遠い頂点の距離 dist2 を求めます（21ー30行目）。こちらも最大49回問い合わせます。

最後に dist2 を表示します。以下が、C++プログラムです。

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

int main()
{
	int n;
	cin >> n;

	int dist1 = 0;
	int dist1_index;
	for (int i = 2; i <= n; ++i) {
		cout << "? " << 1 << " " << i << endl;
		int dist;
		cin >> dist;
		if (dist > dist1) {
			dist1 = dist;
			dist1_index = i;
		}
	}

	int dist2 = 0;
	for (int i = 1; i <= n; ++i) {
		if (i == dist1_index) {
			continue;
		}
		cout << "? " << dist1_index << " " << i << endl;
		int dist;
		cin >> dist;
		dist2 = max(dist2, dist);
	}

	cout << "! " << dist2 << endl;

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

最後に

インタラクティブな問題で、木の直径について理解を深めることができました。

引き続き ABC の問題を紹介していきます。