ABC270-D Stones

問題へのリンク

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("10 2");
            WillReturn.Add("1 4");
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("11 4");
            WillReturn.Add("1 2 3 6");
            //8
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10000 10");
            WillReturn.Add("1 2 4 8 16 32 64 128 256 512");
            //5136
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mN;
    static int[] mAArr;

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        mN = wkArr[0];

        mAArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        Array.Sort(mAArr);

        // 加減法で連立方程式を解く
        int Result = dfs(mN, 0);
        int Answer = (Result + mN) / 2;
        Console.WriteLine(Answer);
    }

    // (高橋君の取得石 - 青木君の取得石) を返す
    static Dictionary<int, int> mMemo = new Dictionary<int, int>();
    static int dfs(int pRest, int pLevel)
    {
        int Hash = pRest * 10 + pLevel;
        if (mMemo.ContainsKey(Hash)) {
            return mMemo[Hash];
        }

        // 先手番か後手番かを求める
        bool IsSente = pLevel == 0;

        var SeniList = new List<int>();
        foreach (int EachA in mAArr) {
            if (EachA > pRest) break;

            int Result = dfs(pRest - EachA, (pLevel + 1) % 2);
            if (IsSente) Result += EachA;
            else Result -= EachA;

            SeniList.Add(Result);
        }

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

解説

A1 = 1 という制約があるので、
先手と後手の得点の総合計は決まってます。

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

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

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

類題

TDP B ゲーム