ABC195-E Lucky 7 Battle

問題へのリンク

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("2");
            WillReturn.Add("35");
            WillReturn.Add("AT");
            //Takahashi
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            WillReturn.Add("12345");
            WillReturn.Add("AAAAT");
            //Aoki
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("5");
            WillReturn.Add("67890");
            WillReturn.Add("TTTTA");
            //Takahashi
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("5");
            WillReturn.Add("12345");
            WillReturn.Add("ATATA");
            //Aoki
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static string mS;
    static string mX;

    static int UB;

    // mod 7[10の乗数] な配列
    static int[] mModPowArr;

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

        mS = InputList[1];
        mX = InputList[2];

        UB = mS.Length - 1;

        mModPowArr = new int[UB + 1];
        int Base = 1;
        for (int I = UB; 0 <= I; I--) {
            mModPowArr[I] = Base % 7;
            Base *= 10;
            Base %= 7;
        }

        // メモ化再帰で解く
        char Result = DFS(0, 0);
        if (Result == 'T') Console.WriteLine("Takahashi");
        if (Result == 'A') Console.WriteLine("Aoki");
    }

    static Dictionary<int, char> mMemoDict = new Dictionary<int, char>();

    static char DFS(int pMod7, int pCurrInd)
    {
        int Hash = GetHash(pMod7, pCurrInd);
        if (mMemoDict.ContainsKey(Hash)) {
            return mMemoDict[Hash];
        }

        if (pCurrInd > UB) {
            char Result = (pMod7 == 0 ? 'T' : 'A');
            return mMemoDict[Hash] = Result;
        }

        var SeniList = new List<char>();

        // 0を選ぶ場合
        SeniList.Add(DFS(pMod7, pCurrInd + 1));

        // 数字を選ぶ場合
        int CurrNum = mS[pCurrInd] - '0';
        int NewMod7 = (pMod7 + CurrNum * mModPowArr[pCurrInd]) % 7;
        SeniList.Add(DFS(NewMod7, pCurrInd + 1));

        char Teban = mX[pCurrInd];
        if (Teban == 'T') {
            if (SeniList.Contains('T')) {
                return mMemoDict[Hash] = 'T';
            }
            return mMemoDict[Hash] = 'A';
        }
        else {
            if (SeniList.Contains('A')) {
                return mMemoDict[Hash] = 'A';
            }
            return mMemoDict[Hash] = 'T';
        }
    }

    static int GetHash(int pMod7, int pCurrInd)
    {
        return pCurrInd * 10 + pMod7;
    }
}

解説

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

類題

ARC038-B マス目と駒