ABC427-D The Simple Game

問題へのリンク

C#のソース

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

class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("4 6 2");
            WillReturn.Add("AABB");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            WillReturn.Add("3 1");
            WillReturn.Add("3 3");
            WillReturn.Add("3 4");
            WillReturn.Add("4 2");
            WillReturn.Add("4 6 2");
            WillReturn.Add("ABAB");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            WillReturn.Add("3 1");
            WillReturn.Add("3 3");
            WillReturn.Add("3 4");
            WillReturn.Add("4 2");
            WillReturn.Add("5 8 3");
            WillReturn.Add("ABABB");
            WillReturn.Add("1 2");
            WillReturn.Add("2 2");
            WillReturn.Add("2 3");
            WillReturn.Add("3 1");
            WillReturn.Add("3 4");
            WillReturn.Add("4 4");
            WillReturn.Add("4 5");
            WillReturn.Add("5 3");
            //Alice
            //Bob
            //Bob
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static long mEdgeCnt;
    static long mMoveCntLimit;
    static char[] mCharArr;

    // 隣接リスト
    static Dictionary<long, List<long>> mToNodeListDict = new Dictionary<long, List<long>>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        int CurrInd = 1;

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        var sb = new System.Text.StringBuilder();
        while (CurrInd <= InputList.Count - 1) {
            SplitAct(InputList[CurrInd]);
            mEdgeCnt = wkArr[1];
            mMoveCntLimit = wkArr[2] * 2;

            mCharArr = InputList[CurrInd + 1].ToCharArray();

            // マルチテストケースなので、メンバ変数のクリア
            mToNodeListDict.Clear();
            mMemo.Clear();

            for (int I = CurrInd + 2; I <= CurrInd + 2 + mEdgeCnt - 1; I++) {
                SplitAct(InputList[I]);
                long FromNode = wkArr[0];
                long ToNode = wkArr[1];
                if (mToNodeListDict.ContainsKey(FromNode) == false) {
                    mToNodeListDict[FromNode] = new List<long>();
                }
                mToNodeListDict[FromNode].Add(ToNode);
            }
            string Result = Solve();
            sb.AppendLine(Result);

            // 不要になった行数を加算
            CurrInd += 2 + (int)mEdgeCnt;
        }
        Console.Write(sb.ToString());
    }

    static string Solve()
    {
        if (IsTebanWin(1, 0)) {
            return "Alice";
        }
        return "Bob";
    }

    static Dictionary<long, bool> mMemo = new Dictionary<long, bool>();
    static bool IsTebanWin(long pCurrNode, long pMoveCnt)
    {
        long Hash = pCurrNode * 100000000 + pMoveCnt;
        if (mMemo.ContainsKey(Hash)) {
            return mMemo[Hash];
        }

        bool IsTebanAlice = (pMoveCnt % 2 == 0);

        if (pMoveCnt == mMoveCntLimit) {
            bool Result;
            if (IsTebanAlice) {
                Result = (mCharArr[pCurrNode - 1] == 'A');
            }
            else {
                Result = (mCharArr[pCurrNode - 1] == 'B');
            }
            return mMemo[Hash] = Result;
        }

        var SeniSet = new HashSet<bool>();
        foreach (long EachToNode in mToNodeListDict[pCurrNode]) {
            SeniSet.Add(IsTebanWin(EachToNode, pMoveCnt + 1));
        }

        if (SeniSet.Contains(false)) {
            return mMemo[Hash] = true;
        }
        return mMemo[Hash] = false;
    }
}

解説

手番の人が勝ちか？ (現在ノード , 移動回数) でメモ化再帰してます。
手番を移動回数の偶奇から求め、
その手番での勝ち負けを判定してます。

コンテストでは、mMemo.Clert()が抜けていて、40分近く溶かしたので
マルチテストケースで、メンバ変数にコレクションを使用する場合は気をつけること