ABC-067-D Fennec VS Snuke

■■■問題■■■

フェネックとすぬけくんがボードゲームで遊んでいます。

このボードゲームには1番からN番までの番号がついたN個のマスと、
マスどうしをつなぐ N-1 本の道が存在しています。

ai番のマスとbi番のマスはi番目の道を介して隣り合っています。
どの2つのマスも隣接するマスをいくつか辿って必ず辿り着くことが可能です。
すなわち、グラフ理論の言葉を用いると、マスと道から構成されるグラフは木です。

はじめに1番のマスは黒く、N番のマスは白く塗られています。その他のマスはまだ色が塗られていません。
先手のフェネックと後手のすぬけくんは残りのマスに交互に色を塗ります。
自分の手番において、2人はそれぞれ以下のような行動を行います。

●フェネック：黒く塗られたマスに隣接したマスであって、色が塗られていないマスを1つ選んで黒く塗る。
●すぬけくん：白く塗られたマスに隣接したマスであって、色が塗られていないマスを1つ選んで白く塗る。

手番のプレイヤーがマスに色を塗ることができなかったとき、敗者となります。
フェネックとすぬけくんが最適に行動したとき勝者はどちらか判定してください。

■■■入力■■■

N
a1 b1
・
・
・
aN-1 bN-1

●2 <= N <= 10万
●1 <= ai,bi <= N
●与えられるグラフは木

■■■出力■■■

勝者がフェネックならばFennecと、すぬけくんならばSnukeと出力せよ。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("7");
            WillReturn.Add("3 6");
            WillReturn.Add("1 2");
            WillReturn.Add("3 1");
            WillReturn.Add("7 4");
            WillReturn.Add("5 7");
            WillReturn.Add("1 4");
            //Fennec
            //例えばフェネックがはじめに2番のマスを黒く塗ると、
            //すぬけくんがどのようにマスを白く塗ったとしてもフェネックが勝者となります。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("1 4");
            WillReturn.Add("4 2");
            WillReturn.Add("2 3");
            //Snuke
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int N;

    //移動先のList[移動元]で辺を表現
    static Dictionary<int, List<int>> EdgeDict = new Dictionary<int, List<int>>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        N = int.Parse(InputList[0]);

        foreach (string EachStr in InputList.Skip(1)) {
            int[] wkArr = EachStr.Split(' ').Select(X => int.Parse(X)).ToArray();

            if (EdgeDict.ContainsKey(wkArr[0]) == false) {
                EdgeDict.Add(wkArr[0], new List<int>());
            }
            EdgeDict[wkArr[0]].Add(wkArr[1]);

            if (EdgeDict.ContainsKey(wkArr[1]) == false) {
                EdgeDict.Add(wkArr[1], new List<int>());
            }
            EdgeDict[wkArr[1]].Add(wkArr[0]);
        }
        int[] KyoriArr1 = DeriveKyori(1);
        int[] KyoriArr2 = DeriveKyori(N);

        for (int I = 1; I <= KyoriArr1.GetUpperBound(0); I++) {
            Console.WriteLine("KyoriArr1[{0}]={1}", I, KyoriArr1[I]);
        }
        Console.WriteLine();
        for (int I = 1; I <= KyoriArr2.GetUpperBound(0); I++) {
            Console.WriteLine("KyoriArr2[{0}]={1}", I, KyoriArr2[I]);
        }
        Console.WriteLine();

        int Node1Cnt = 0;
        int Node2Cnt = 0;
        for (int I = 1; I <= N; I++) {
            if (KyoriArr1[I] <= KyoriArr2[I]) Node1Cnt++;
            else Node2Cnt++;
        }
        Console.WriteLine(Node1Cnt > Node2Cnt ? "Fennec" : "Snuke");
    }

    struct JyoutaiDef
    {
        internal int CurrNode;
        internal int Level;
    }

    //始点のノードを引数として、各ノードまでの距離を返す
    static int[] DeriveKyori(int pNode)
    {
        int[] KyoriArr = new int[N + 1];

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrNode = pNode;
        WillEnqueue.Level = 0;

        Que.Enqueue(WillEnqueue);
        var VisitedSet = new HashSet<int>();

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            if (VisitedSet.Add(Dequeued.CurrNode) == false) continue;
            KyoriArr[Dequeued.CurrNode] = Dequeued.Level;

            if (EdgeDict.ContainsKey(Dequeued.CurrNode)) {
                foreach (int EachNode in EdgeDict[Dequeued.CurrNode]) {
                    WillEnqueue.CurrNode = EachNode;
                    WillEnqueue.Level = Dequeued.Level + 1;
                    Que.Enqueue(WillEnqueue);
                }
            }
        }
        return KyoriArr;
    }
}

デバッグ情報付の実行結果

KyoriArr1[1]=0
KyoriArr1[2]=1
KyoriArr1[3]=1
KyoriArr1[4]=1
KyoriArr1[5]=3
KyoriArr1[6]=2
KyoriArr1[7]=2

KyoriArr2[1]=2
KyoriArr2[2]=3
KyoriArr2[3]=3
KyoriArr2[4]=1
KyoriArr2[5]=1
KyoriArr2[6]=4
KyoriArr2[7]=0

Fennec

解説

最初に、幅優先探索でノードごとの
ノード1からの距離と、ノードNからの距離を求めてます。

次に、フェネックとすぬけくんが最適戦略を取ったときに、
どっちのノードになるかを判定してます。