AtCoderのARC
次のARCの問題へ
前のARCの問題へ
ARC142-C Tree Queries
C#のソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main()
{
int N = int.Parse(Console.ReadLine());
// ノード1からの距離[ノード]
var DistanceDict1 = new Dictionary<int, int>();
// ノード2からの距離[ノード]
var DistanceDict2 = new Dictionary<int, int>();
for (int I = 1; I <= N; I++) {
int ToNode = I;
if (1 + ToNode > 3 && ToNode != 1) {
Console.WriteLine("? {0} {1}", 1, ToNode);
DistanceDict1[ToNode] = int.Parse(Console.ReadLine());
}
if (2 + ToNode > 3 && ToNode != 2) {
Console.WriteLine("? {0} {1}", 2, ToNode);
DistanceDict2[ToNode] = int.Parse(Console.ReadLine());
}
}
var AnswerKouhoList = new List<int>();
for (int I = 3; I <= N; I++) {
AnswerKouhoList.Add(DistanceDict1[I] + DistanceDict2[I]);
}
int MinDistance = AnswerKouhoList.Min();
if (MinDistance != 3) {
Console.WriteLine("! {0}", MinDistance);
return;
}
// 最小距離が3なら場合分けが必要
var NodeList = new List<int>();
if (MinDistance == 3) {
for (int I = 3; I <= N; I++) {
if (DistanceDict1[I] + DistanceDict2[I] == 3) {
NodeList.Add(I);
}
}
}
if (NodeList.Count == 1) {
Console.WriteLine("! 1");
return;
}
int Node1 = NodeList[0];
int Node2 = NodeList[1];
Console.WriteLine("? {0} {1}", Node1, Node2);
int Distance = int.Parse(Console.ReadLine());
if (Distance == 1) {
Console.WriteLine("! 3");
return;
}
else {
Console.WriteLine("! 1");
return;
}
}
}
解説
最初に
ノード1から各ノードへの距離
ノード2から各ノードへの距離
を聞きます。
これで、各ノードを経由する場合の距離を網羅できます。
distance(ノード1 , 経由ノード ) + distance(ノード2 , 経由ノード)
の最小値が解候補になります。
例外として、
ノード1とノード2が直通の場合は、距離が3になってしまうので
距離が3になる経由ノードを列挙します。
距離が3になる経由ノードが1ノードしかなければ、ノード1とノード2は直通です。
距離が3になる経由ノードが2ノード以上あったら、
そのノード同士の距離を問い合わせて、1なら、ノード1とノード2は直通でないです。
下記のようなグラフを書くと分かりやすいです。
ノード1とノード2が直通の場合1
○ー1ー2ー○
\
○
ノード1とノード2が直通の場合2
1ー2ー○
ノード1とノード2が直通でない場合
1ー○ー○ー2