AtCoder

ABC019 D問題(高橋くんと木の直径)を解く

AtCoder_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 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA