ABC359-D Avoid K Palindrome

問題へのリンク

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("7 4");
            WillReturn.Add("AB?A?BA");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("40 7");
            WillReturn.Add("????????????????????????????????????????");
            //116295436
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("15 5");
            WillReturn.Add("ABABA??????????");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("40 8");
            WillReturn.Add("?A?B??B?B?AA?A?B??B?A???B?BB?B???BA??BAA");
            //259240
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 998244353;

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

        char[] SArr = InputList[1].ToCharArray();

        // 場合の数[現在の文字列]
        var PrevDP = new Dictionary<string, long>();
        PrevDP[""] = 1;

        for (long I = 0; I <= SArr.GetUpperBound(0); I++) {
            var CurrDP = new Dictionary<string, long>();
            foreach (var EachPair in PrevDP) {
                Action<string> AddAct = (pNewStr) =>
                {
                    if (pNewStr.Length > K) {
                        pNewStr = pNewStr.Substring(1, (int)K);
                    }
                    if (pNewStr.Length == K) {
                        if (IsKaibun(pNewStr)) {
                            return;
                        }
                    }

                    if (CurrDP.ContainsKey(pNewStr) == false) {
                        CurrDP[pNewStr] = 0;
                    }
                    CurrDP[pNewStr] += EachPair.Value;
                    CurrDP[pNewStr] %= Hou;
                };

                if (SArr[I] == 'A') {
                    AddAct(EachPair.Key + "A");
                }
                if (SArr[I] == 'B') {
                    AddAct(EachPair.Key + "B");
                }
                if (SArr[I] == '?') {
                    AddAct(EachPair.Key + "A");
                    AddAct(EachPair.Key + "B");
                }
            }
            PrevDP = CurrDP;
        }

        long Answer = 0;
        foreach (long EachVal in PrevDP.Values) {
            Answer += EachVal;
            Answer %= Hou;
        }
        Console.WriteLine(Answer);
    }

    ////////////////////////////////////////////////////////////////
    // String型を引数とし、回文判定を行う
    ////////////////////////////////////////////////////////////////
    static bool IsKaibun(string pStr)
    {
        int UB = pStr.Length - 1;
        for (int I = 0; I <= UB / 2; I++) {
            int PairInd = UB - I;
            if (pStr[I] != pStr[PairInd]) {
                return false;
            }
        }
        return true;
    }
}

解説

場合の数[現在の文字列] でDPしてます。

DPの計算量は、O(状態数 * 遷移数)なので
状態数削減のため、
現在の文字列がN文字を超えたら、末尾N文字以外は捨ててます。

回文判定は都度行ってます。