ABC308-E MEX

問題へのリンク

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("1 1 0 2");
            WillReturn.Add("MEEX");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("0 0 0");
            WillReturn.Add("XXX");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("15");
            WillReturn.Add("1 1 2 0 0 2 0 2 0 0 0 0 0 2 2");
            WillReturn.Add("EXMMXXXEMEXEXMM");
            //13
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] AArr = InputList[1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
        string S = InputList[2];
        char[] CharArr = S.ToCharArray();

        // 場合の数[状態][BitSet]なDP表
        int AllBitOn = (1 << 3) - 1;
        long[,] PrevDP = new long[4, AllBitOn + 1];
        PrevDP[0, 0] = 1;

        for (int I = 0; I <= CharArr.GetUpperBound(0); I++) {
            long[,] CurrDP = (long[,])PrevDP.Clone();

            for (int J = 0; J <= 2; J++) {
                for (int K = 0; K <= AllBitOn; K++) {
                    if (PrevDP[J, K] == 0) continue;

                    bool CanSeni = false;
                    if (J == 0 && CharArr[I] == 'M') CanSeni = true;
                    if (J == 1 && CharArr[I] == 'E') CanSeni = true;
                    if (J == 2 && CharArr[I] == 'X') CanSeni = true;
                    if (CanSeni == false) continue;

                    int NewJ = J + 1;
                    int MapVal = 0;
                    if (AArr[I] == 0) MapVal = 1;
                    if (AArr[I] == 1) MapVal = 2;
                    if (AArr[I] == 2) MapVal = 4;
                    int NewK = K | MapVal;

                    CurrDP[NewJ, NewK] += PrevDP[J, K];
                }
            }
            PrevDP = CurrDP;
        }

        long Answer = 0;
        for (int K = 0; K <= AllBitOn; K++) {
            long Mex = GetMex(K);
            if (PrevDP[3, K] > 0) {
                Answer += Mex * PrevDP[3, K];
            }
        }
        Console.WriteLine(Answer);
    }

    // BitSetを引数としてMexを返す
    static long GetMex(int pBitSet)
    {
        var ValList = new List<int>();
        if ((pBitSet & 1) > 0) ValList.Add(0);
        if ((pBitSet & 2) > 0) ValList.Add(1);
        if ((pBitSet & 4) > 0) ValList.Add(2);

        for (int I = 0; I <= 3; I++) {
            if (ValList.Contains(I)) continue;
            return I;
        }
        throw new Exception();
    }
}

解説

場合の数[状態][BitSet]なDPで解いてます。

状態は、
0 選択なし
1 Mを選択
2 Eを選択
3 Xを選択
で対応させ、

BitSetは、0を1、1を2、2を4で対応させてます。

遷移において、状態は、必ずインクリメントされるので
インラインDPにすることもできます。