A35 Game 4

問題へのリンク

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("4");
            WillReturn.Add("20 10 30 40");
            //30
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mN;
    static int[] mAArr;

    // 隣接リスト
    static Dictionary<int, List<int>> mToNodeListDict = new Dictionary<int, List<int>>();

    static List<int[]> mNumArrList = new List<int[]>();

    // 得点[葉ノード]なDict
    static Dictionary<int, int> mLeafNodeScoreDict = new Dictionary<int, int>();

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

        // ピラミッドのノードに番号を振る
        int CurrNode = 0;
        for (int I = 1; I <= mN; I++) {
            var NumList = new List<int>();
            for (int J = 1; J <= I; J++) {
                NumList.Add(CurrNode++);
            }
            mNumArrList.Add(NumList.ToArray());
        }

        // 隣接リストを作成
        for (int I = 0; I <= mNumArrList.Count - 2; I++) {
            int[] CurrArr = mNumArrList[I];
            int[] NextArr = mNumArrList[I + 1];

            for (int J = 0; J <= CurrArr.GetUpperBound(0); J++) {
                int FromNode = CurrArr[J];
                if (mToNodeListDict.ContainsKey(FromNode) == false) {
                    mToNodeListDict[FromNode] = new List<int>();
                }
                int ToNode1 = NextArr[J];
                int ToNode2 = NextArr[J + 1];
                mToNodeListDict[FromNode].Add(ToNode1);
                mToNodeListDict[FromNode].Add(ToNode2);
            }
        }

        // 葉ノードの得点をDictに設定
        int[] LeafNumArr = mNumArrList.Last();
        for (int I = 0; I <= LeafNumArr.GetUpperBound(0); I++) {
            mLeafNodeScoreDict[LeafNumArr[I]] = mAArr[I];
        }

        Console.WriteLine(dfs(0, true));
    }

    static Dictionary<int, int> mMemo = new Dictionary<int, int>();
    static int dfs(int pCurrNode, bool IsSente)
    {
        int Hash = GetHash(pCurrNode, IsSente);
        if (mMemo.ContainsKey(Hash)) {
            return mMemo[Hash];
        }

        if (mLeafNodeScoreDict.ContainsKey(pCurrNode)) {
            return mLeafNodeScoreDict[pCurrNode];
        }

        var SeniList = new List<int>();
        foreach (int EachToNode in mToNodeListDict[pCurrNode]) {
            SeniList.Add(dfs(EachToNode, IsSente == false));
        }

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

    static int GetHash(int pCurrNode, bool IsSente)
    {
        return pCurrNode * 2 + (IsSente ? 1 : 0);
    }
}

解説

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