ABC354-E Remove Pairs

問題へのリンク

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("5");
            WillReturn.Add("1 9");
            WillReturn.Add("2 5");
            WillReturn.Add("4 9");
            WillReturn.Add("1 4");
            WillReturn.Add("2 5");
            //Aoki
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("9");
            WillReturn.Add("3 2");
            WillReturn.Add("1 7");
            WillReturn.Add("4 1");
            WillReturn.Add("1 8");
            WillReturn.Add("5 2");
            WillReturn.Add("9 8");
            WillReturn.Add("2 1");
            WillReturn.Add("6 8");
            WillReturn.Add("5 2");
            //Takahashi
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct CardInfoDef
    {
        internal int Omote;
        internal int Ura;
    }
    static List<CardInfoDef> mCardInfoList = new List<CardInfoDef>();

    static List<int> mBitList = new List<int>();

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

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            CardInfoDef WillAdd;
            WillAdd.Omote = wkArr[0];
            WillAdd.Ura = wkArr[1];
            mCardInfoList.Add(WillAdd);
        }

        int Beki2 = 1;
        for (int I = 0; I <= mCardInfoList.Count - 1; I++) {
            mBitList.Add(Beki2);
            Beki2 *= 2;
        }

        if (IsSenteWin(0)) {
            Console.WriteLine("Takahashi");
        }
        else {
            Console.WriteLine("Aoki");
        }
    }

    // 未選択なBitSetを引数として、先手が勝ちかを返す
    static Dictionary<int, bool> mMemo = new Dictionary<int, bool>();
    static bool IsSenteWin(int pBitSet)
    {
        if (mMemo.ContainsKey(pBitSet)) {
            return mMemo[pBitSet];
        }

        var SeniSet = new HashSet<bool>();
        for (int I = 0; I <= mBitList.Count - 1; I++) {
            // 再使用は不可
            if ((pBitSet & mBitList[I]) > 0) continue;
            for (int J = I + 1; J <= mBitList.Count - 1; J++) {
                // 再使用は不可
                if ((pBitSet & mBitList[J]) > 0) continue;

                bool CanSeni = false;

                // 表が一致
                if (mCardInfoList[I].Omote == mCardInfoList[J].Omote) {
                    CanSeni = true;
                }

                // 裏が一致
                if (mCardInfoList[I].Ura == mCardInfoList[J].Ura) {
                    CanSeni = true;
                }

                if (CanSeni) {
                    SeniSet.Add(IsSenteWin(pBitSet + mBitList[I] + mBitList[J]));
                }
            }
        }

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

解説

メモ化再帰で解いてます。