ABC363-C Avoid K Palindrome 2

問題へのリンク

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("3 2");
            WillReturn.Add("aab");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 3");
            WillReturn.Add("zzyyx");
            //16
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 5");
            WillReturn.Add("abcwxyzyxw");
            //440640
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    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);

        if (mCharArr.Distinct().Count() == mCharArr.Length) {
            int SpecialAnswer = 1;
            for (int I = 1; I <= mCharArr.Length; I++) {
                SpecialAnswer *= I;
            }
            Console.WriteLine(SpecialAnswer);
            return;
        }

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrStr = "";
        WillPush.UsedBit = 0;
        Stk.Push(WillPush);

        int GoalLen = mCharArr.Length;
        int Answer = 0;

        var VisitedSet = new HashSet<string>();

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            // クリア判定
            if (Popped.CurrStr.Length == GoalLen) {
                Answer++;
                continue;
            }

            for (int I = 0; I <= UB; I++) {
                int CurrBit = (1 << I);
                if ((Popped.UsedBit & CurrBit) > 0) continue;

                WillPush.CurrStr = Popped.CurrStr + mCharArr[I];

                int CurrInd = WillPush.CurrStr.Length - 1;
                int PrevInd = CurrInd - mK + 1;
                if (PrevInd >= 0) {
                    if (WillPush.CurrStr[CurrInd] == WillPush.CurrStr[PrevInd]) {
                        string SubStr = WillPush.CurrStr.Substring(PrevInd);
                        if (IsKaibun(SubStr)) {
                            continue;
                        }
                    }
                }

                if (VisitedSet.Add(WillPush.CurrStr) == false) {
                    continue;
                }

                WillPush.UsedBit = Popped.UsedBit + CurrBit;
                Stk.Push(WillPush);
            }
        }
        Console.WriteLine(Answer);
    }

    struct JyoutaiDef
    {
        internal string CurrStr;
        internal int UsedBit;
    }

    ////////////////////////////////////////////////////////////////
    // 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;
    }
}

解説

10の階乗 = 3628800
で、順列を列挙してから、
回文判定するとTLEするので、
DFSで、回文判定しながら、順列を列挙してます。

DFSの定数倍高速化で
●VisitedSetで同じ文字列を回避する
●BitSetを使用する
●新しく増えた箇所のみ回文判定を行う
といった手法を使ってます。

最悪計算量を減らす対策で、
最初に、文字がdistinctかの判定もしてます。