ABC349-E Weighted Tic-Tac-Toe

問題へのリンク

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

    static int[,] mScoreArr;
    static int UB = 2;

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

        char[,] BanArr = new char[UB + 1, UB + 1];
        for (long X = 0; X <= UB; X++) {
            for (long Y = 0; Y <= UB; Y++) {
                BanArr[X, Y] = '?';
            }
        }

        if (IsWin(BanArr)) {
            Console.WriteLine("Takahashi");
        }
        else {
            Console.WriteLine("Aoki");
        }
    }

    // 盤面を引数として、手番を持った方が勝ちかを返す
    static Dictionary<long, bool> mMemo = new Dictionary<long, bool>();
    static bool IsWin(char[,] pBanArr)
    {
        long CurrHash = GetHash(pBanArr);
        if (mMemo.ContainsKey(CurrHash)) return mMemo[CurrHash];

        long SpaceCnt;
        long TScore;
        long AScore;
        GetGameInfo(pBanArr, out SpaceCnt, out TScore, out AScore);

        bool TebanT = SpaceCnt % 2 == 1;

        if (TebanT) {
            if (IsBingo(pBanArr, 'T')) {
                return true;
            }
            if (IsBingo(pBanArr, 'A')) {
                return false;
            }
        }
        else {
            if (IsBingo(pBanArr, 'A')) {
                return true;
            }
            if (IsBingo(pBanArr, 'T')) {
                return false;
            }
        }

        if (SpaceCnt == 0) {
            if (TScore > AScore) {
                return false;
            }
            return true;
        }

        var SeniList = new List<char[,]>();
        for (long X = 0; X <= UB; X++) {
            for (long Y = 0; Y <= UB; Y++) {
                if (pBanArr[X, Y] == '?') {
                    char[,] NewBanArr = (char[,])pBanArr.Clone();
                    NewBanArr[X, Y] = (TebanT ? 'T' : 'A');
                    SeniList.Add(NewBanArr);
                }
            }
        }

        // 相手を負けにできる手が、少なくとも1つあれば手番を持ったほうの勝ち
        if (SeniList.Exists(pX => IsWin(pX) == false)) {
            return mMemo[CurrHash] = true;
        }
        return mMemo[CurrHash] = false;
    }

    // ビンゴ判定
    static bool IsBingo(char[,] pBanArr, char pChar)
    {
        char[,] wkP = pBanArr;

        // 横
        if (wkP[0, 0] == pChar && wkP[1, 0] == pChar && wkP[2, 0] == pChar) return true;
        if (wkP[0, 1] == pChar && wkP[1, 1] == pChar && wkP[2, 1] == pChar) return true;
        if (wkP[0, 2] == pChar && wkP[1, 2] == pChar && wkP[2, 2] == pChar) return true;

        // 縦
        if (wkP[0, 0] == pChar && wkP[0, 1] == pChar && wkP[0, 2] == pChar) return true;
        if (wkP[1, 0] == pChar && wkP[1, 1] == pChar && wkP[1, 2] == pChar) return true;
        if (wkP[2, 0] == pChar && wkP[2, 1] == pChar && wkP[2, 2] == pChar) return true;

        // 斜め
        if (wkP[0, 0] == pChar && wkP[1, 1] == pChar && wkP[2, 2] == pChar) return true;
        if (wkP[0, 2] == pChar && wkP[1, 1] == pChar && wkP[2, 0] == pChar) return true;

        return false;
    }

    // 盤面を引数として、ゲームの状態を返す
    static void GetGameInfo(char[,] pBanArr, out long pSpaceCnt, out long pTScore, out long pAScore)
    {
        pSpaceCnt = pTScore = pAScore = 0;
        for (long X = 0; X <= UB; X++) {
            for (long Y = 0; Y <= UB; Y++) {
                if (pBanArr[X, Y] == '?') pSpaceCnt++;
                if (pBanArr[X, Y] == 'T') pTScore += mScoreArr[X, Y];
                if (pBanArr[X, Y] == 'A') pAScore += mScoreArr[X, Y];
            }
        }
    }

    // 盤面のハッシュ値を返す
    static long GetHash(char[,] pBanArr)
    {
        long Hash = 0;
        for (long X = 0; X <= UB; X++) {
            for (long Y = 0; Y <= UB; Y++) {
                if (pBanArr[X, Y] == 'A') Hash += 1;
                if (pBanArr[X, Y] == 'T') Hash += 2;
                Hash *= 10;
            }
        }
        return Hash;
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をintの2次元配列に設定する
    ////////////////////////////////////////////////////////////////
    static int[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new int[0, 0];
        }

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

        SplitAct(StrList[0]);

        int UB_X = IntArr.GetUpperBound(0);
        int UB_Y = StrList.Count - 1;

        int[,] WillReturn = new int[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            SplitAct(StrList[Y]);
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = IntArr[X];
            }
        }
        return WillReturn;
    }
}

解説

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