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が直通の場合2
１ー２ー○

ノード1とノード2が直通でない場合
１ー○ー○ー２