TDP B ゲーム

問題へのリンク

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

    static int[] mAArr;
    static int[] mBArr;

    static int UB_A;
    static int UB_B;

    static void Main()
    {
        List<string> InputList = GetInputList();
        mAArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        mBArr = InputList[2].Split(' ').Select(pX => int.Parse(pX)).ToArray();

        UB_A = mAArr.GetUpperBound(0);
        UB_B = mBArr.GetUpperBound(0);

        int Result = DFS(0, 0);

        // 加減法で連立方程式を解く
        int SumVal = mAArr.Sum() + mBArr.Sum();
        int Answer = (Result + SumVal) / 2;
        Console.WriteLine(Answer);
    }

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

    static int DFS(int pAInd, int pBInd)
    {
        int Hash = pAInd * 10000 + pBInd;
        if (mMemoDict.ContainsKey(Hash)) {
            return mMemoDict[Hash];
        }

        // 先手番か後手番かを求める
        int IndSum = pAInd + pBInd;
        bool IsSente = IndSum % 2 == 0;

        var SeniList = new List<int>();
        if (pAInd <= UB_A) {
            int Result = DFS(pAInd + 1, pBInd);
            if (IsSente) Result += mAArr[pAInd];
            else Result -= mAArr[pAInd];
            SeniList.Add(Result);
        }
        if (pBInd <= UB_B) {
            int Result = DFS(pAInd, pBInd + 1);
            if (IsSente) Result += mBArr[pBInd];
            else Result -= mBArr[pBInd];
            SeniList.Add(Result);
        }

        if (SeniList.Count > 0) {
            if (IsSente) return mMemoDict[Hash] = SeniList.Max();
            return mMemoDict[Hash] = SeniList.Min();
        }
        return mMemoDict[Hash] = 0;
    }
}

解説

先手と後手の得点の総合計は決まってます。

先手の得点 - 後手の得点 をSとおいて
先手はSを最大化しようとして
後手はSを最小化しようとします。

後は、メモ化再帰で
先手は遷移可能な状態からSが最大の状態を選び
後手は遷移可能な状態からSが最小の状態を選ぶ
ようにします。

先手の合計 + 後手の合計 は、最初から分かるので
先手の合計 - 後手の合計 をメモ化再帰で求めれば、後は、
加減法で連立方程式を解いて、答えが分かります。

類題

EDP L Deque