第5回PAST K 的あて

問題へのリンク

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("#...");
            WillReturn.Add("....");
            WillReturn.Add("....");
            WillReturn.Add("....");
            //5.0000000000
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("#...");
            WillReturn.Add("#...");
            WillReturn.Add("....");
            WillReturn.Add("....");
            //7.5000000000
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add(".#..");
            WillReturn.Add("#.#.");
            WillReturn.Add(".#..");
            WillReturn.Add("....");
            //10.4166666667
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("###.");
            WillReturn.Add("####");
            WillReturn.Add("####");
            WillReturn.Add("####");
            //32.5674089515
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int UB = 4 - 1;

    static void Main()
    {
        List<string> InputList = GetInputList();
        for (int I = 0; I <= InputList.Count - 1; I++) {
            InputList[I] = InputList[I].Replace('.', '1').Replace('#', '0');
        }

        char[,] BanArr = CreateBanArr(InputList);

        int Hash = GetHash(BanArr);
        double Answer = dfs(GetHash(BanArr));
        Console.WriteLine(Answer);
    }

    // メモ化再帰
    static Dictionary<int, double> mMemo = new Dictionary<int, double>();
    static double dfs(int pHash)
    {
        if (mMemo.ContainsKey(pHash)) {
            return mMemo[pHash];
        }

        char[,] CurrBanArr = GetBan(pHash);

        var SeniList = new List<double>();
        for (int LoopX = 0; LoopX <= UB; LoopX++) {
            for (int LoopY = 0; LoopY <= UB; LoopY++) {
                List<PointDef> KinbouMatoList = DeriveKinbouMatoList(LoopX, LoopY, CurrBanArr);
                if (KinbouMatoList.Count == 0) continue;

                var KouhoList = new List<double>();

                // 1の場合は、コンプガチャ問題の期待値
                if (KinbouMatoList.Count == 1) {
                    SeniList.Add(5 + dfs(dfsHelp(CurrBanArr, KinbouMatoList[0])));
                }
                // 外れが無い場合
                else if (KinbouMatoList.Count == 5) {
                    foreach (PointDef EachPoint in KinbouMatoList) {
                        KouhoList.Add(1D / 5D * dfs(dfsHelp(CurrBanArr, EachPoint)));
                    }
                    SeniList.Add(1 + KouhoList.Sum());
                }
                else { // 外れがある場合
                    int KinbouMatoCnt = KinbouMatoList.Count;
                    // 自己ループ以外になる確率
                    double NonLoopProb = KinbouMatoCnt / 5D;

                    double NewEx = 1D / NonLoopProb; // 自己ループ以外になる確率の逆数

                    foreach (PointDef EachPoint in KinbouMatoList) {
                        KouhoList.Add(1D / KinbouMatoCnt * dfs(dfsHelp(CurrBanArr, EachPoint)));
                    }
                    // 自己ループ以外の条件付確率 * 期待値を集計
                    NewEx += KouhoList.Sum();

                    SeniList.Add(NewEx);
                }
            }
        }

        if (SeniList.Count == 0) return mMemo[pHash] = 0D;
        return mMemo[pHash] = SeniList.Min();
    }

    // 2次元配列の、引数の座標を1にUpdateし、ハッシュ値を返す
    static int dfsHelp(char[,] pBanArr, PointDef pPoint)
    {
        pBanArr[pPoint.X, pPoint.Y] = '1';
        int Hash = GetHash(pBanArr);
        pBanArr[pPoint.X, pPoint.Y] = '0';
        return Hash;
    }

    struct PointDef
    {
        internal int X;
        internal int Y;
    }

    // 4近傍の的の座標のListを返す
    static List<PointDef> DeriveKinbouMatoList(int pBaseX, int pBaseY, char[,] pBanArr)
    {
        var WillReturn = new List<PointDef>();
        Action<int, int> AddAct = (pX, pY) =>
        {
            if (pX < 0 || UB < pX) return;
            if (pY < 0 || UB < pY) return;
            if (pBanArr[pX, pY] == '0') {
                PointDef WillAdd;
                WillAdd.X = pX;
                WillAdd.Y = pY;
                WillReturn.Add(WillAdd);
            }
        };
        AddAct(pBaseX, pBaseY);
        AddAct(pBaseX, pBaseY - 1);
        AddAct(pBaseX, pBaseY + 1);
        AddAct(pBaseX - 1, pBaseY);
        AddAct(pBaseX + 1, pBaseY);
        return WillReturn;
    }

    // ハッシュ値から盤面を求める
    static char[,] GetBan(int pHash)
    {
        char[,] WillReturn = new char[UB + 1, UB + 1];
        for (int X = UB; 0 <= X; X--) {
            for (int Y = UB; 0 <= Y; Y--) {
                if (pHash % 2 == 1) {
                    WillReturn[X, Y] = '1';
                }
                else {
                    WillReturn[X, Y] = '0';
                }
                pHash /= 2;
            }
        }
        return WillReturn;
    }

    // 盤面のハッシュ値を求める
    static int GetHash(char[,] pBanArr)
    {
        int WillReturn = 0;
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                if (pBanArr[X, Y] == '1') WillReturn++;
                if (X != UB || Y != UB) {
                    WillReturn *= 2;
                }
            }
        }
        return WillReturn;
    }

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

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

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

解説

期待値の最小値[盤面のハッシュ値] を更新する
メモ化再帰で解いてます。

類題

TDP J ボール