ABC375-D ABA

問題へのリンク

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("ABCACC");
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("OOOOOOOO");
            //56
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("XYYXYYXYXXX");
            //75
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        char[] CharArr = InputList[0].ToCharArray();
        int UB = CharArr.GetUpperBound(0);

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

        long Answer = 0;
        foreach (char EachChar in CharArr) {
            var CurrDP = new Dictionary<string, long>(PrevDP);
            foreach (var EachPair in PrevDP) {
                string NewKey = EachPair.Key + EachChar.ToString();
                if (NewKey.Length == 2) {
                    NewKey = EachPair.Key + "A";
                }
                if (NewKey.Length == 3) {
                    if (IsKaibun(NewKey)) {
                        Answer += EachPair.Value;
                    }
                    continue;
                }

                if (CurrDP.ContainsKey(NewKey) == false) {
                    CurrDP[NewKey] = 0;
                }
                CurrDP[NewKey] += EachPair.Value;
            }
            PrevDP = CurrDP;
        }
        Console.WriteLine(Answer);
    }

    static bool IsKaibun(string pStr)
    {
        return pStr[0] == pStr[2];
    }
}

解説

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

DPの計算量は、状態数 * 遷移ですが
3文字回文の2文字目を、Aに変換することで状態数を減らし、
TLEを回避してます。