ARC036-C 偶然ジェネレータ

問題へのリンク

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("9 4");
            WillReturn.Add("?011?1110");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("9 3");
            WillReturn.Add("?011?1110");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9 1");
            WillReturn.Add("???1?????");
            //1
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("12 5");
            WillReturn.Add("???0??1??11?");
            //172
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const int Hou = 1000000007;

    static int mK;
    static char[] mCharArr;
    static int UB;

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

        mCharArr = InputList[1].ToCharArray();
        UB = mCharArr.GetUpperBound(0);
        for (int I = 0; I <= UB; I++) {
            if (mCharArr[I] == '0') {
                mCharArr[I] = '-';
            }
            if (mCharArr[I] == '1') {
                mCharArr[I] = '+';
            }
        }

        int Answer = 0;
        for (int I = -mK; I <= 0; I++) {
            int CurrAnswer = ExecDP(I, I + mK);
            Answer += CurrAnswer;
            Answer %= Hou;
        }
        Console.WriteLine(Answer);
    }

    static int ExecDP(int pMinRunSum, int pMaxRunSum)
    {
        // 場合の数[状態]なDP表
        var PrevDP = new Dictionary<int, int>();
        JyoutaiDef FirstJyoutai;
        FirstJyoutai.CurrRunSum = 0;
        FirstJyoutai.AchieveMin = 0;
        if (FirstJyoutai.CurrRunSum == pMinRunSum) {
            FirstJyoutai.AchieveMin = 1;
        }
        int FirshHash = GetHash(FirstJyoutai);
        PrevDP[FirshHash] = 1;

        foreach (char EachChar in mCharArr) {
            var CurrDP = new Dictionary<int, int>();
            foreach (var EachPair in PrevDP) {
                JyoutaiDef CurrJyoutai = GetJyoutai(EachPair.Key);

                Action<int> UpdateAct = (pNewRunSum) =>
                {
                    if (pMinRunSum <= pNewRunSum && pNewRunSum <= pMaxRunSum) {
                        JyoutaiDef NewJyoutai;
                        NewJyoutai.CurrRunSum = pNewRunSum;
                        NewJyoutai.AchieveMin = CurrJyoutai.AchieveMin;
                        if (pNewRunSum == pMinRunSum) {
                            NewJyoutai.AchieveMin = 1;
                        }
                        int NewHash = GetHash(NewJyoutai);
                        if (CurrDP.ContainsKey(NewHash) == false) {
                            CurrDP[NewHash] = 0;
                        }
                        CurrDP[NewHash] += EachPair.Value;
                        CurrDP[NewHash] %= Hou;
                    }
                };

                if (EachChar == '-') {
                    UpdateAct(CurrJyoutai.CurrRunSum - 1);
                }
                if (EachChar == '+') {
                    UpdateAct(CurrJyoutai.CurrRunSum + 1);
                }
                if (EachChar == '?') {
                    UpdateAct(CurrJyoutai.CurrRunSum - 1);
                    UpdateAct(CurrJyoutai.CurrRunSum + 1);
                }
            }
            PrevDP = CurrDP;
        }

        int CurrAnswer = 0;
        foreach (var EachPair in PrevDP) {
            JyoutaiDef CurrJyoutai = GetJyoutai(EachPair.Key);
            if (CurrJyoutai.AchieveMin == 1) {
                CurrAnswer += EachPair.Value;
                CurrAnswer %= Hou;
            }
        }
        return CurrAnswer;
    }

    struct JyoutaiDef
    {
        internal int CurrRunSum; // RunSum (-300から300なので、500を下駄とする)
        internal int AchieveMin; // 最小値達成有無 (0か1)
    }

    static int GetHash(JyoutaiDef pJyoutai)
    {
        int Hash = 0;
        Hash += pJyoutai.CurrRunSum + 500;
        Hash *= 10;
        Hash += pJyoutai.AchieveMin;
        return Hash;
    }

    static JyoutaiDef GetJyoutai(int pHash)
    {
        JyoutaiDef Jyoutai;
        Jyoutai.AchieveMin = pHash % 10;
        pHash /= 10;

        Jyoutai.CurrRunSum = pHash - 500;

        return Jyoutai;
    }
}

解説

0を-1
1を+1
をして考えます。

オセロセットで考察すると、
累積和の最小値と、累積和の最大値の差がK以下なら、
最大の差はK以下であると分かります。

　　　　　　　　●
　　　　　　　●
　　　　　　●
　●　　　●
●　●　●
　　　●

場合の数[累積和 , 累積和の最小値 , 累積和の最大値]
でDPするとTLEになります。

なので
{累積和の最小値 , 累積和の最大値} のペアを決めて、
複数回DPをすることを考えると

場合の数[累積和 , 累積和の最小値に到達したか？]
で重複対応として、
累積和の最小値に到達した場合のみ解に計上することで、
解けます。