ARC155-A ST and TS 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("2");
            WillReturn.Add("6 2");
            WillReturn.Add("abbaab");
            WillReturn.Add("5 3");
            WillReturn.Add("abcbb");
            //Yes
            //No
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("12 400378271514996652");
            WillReturn.Add("njvhhvjnnjvh");
            WillReturn.Add("10 884633988115575508");
            WillReturn.Add("rrhiyvrrur");
            WillReturn.Add("36 71630165869626180");
            WillReturn.Add("vsxmxajrrduhhudrrjaxmxsvvsxmxajrrduh");
            //Yes
            //No
            //Yes
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        var sb = new System.Text.StringBuilder();
        for (int I = 1; I <= InputList.Count - 1; I += 2) {
            SplitAct(InputList[I]);
            long K = wkArr[1];
            string S = InputList[I + 1];
            bool Result = Solve(K, S);

            sb.AppendLine(Result ? "Yes" : "No");
        }
        Console.Write(sb.ToString());
    }

    struct JyoutaiDef
    {
        internal long CurrNode;
        internal char NodeVal;
        internal long Level;
    }

    static bool Solve(long pK, string pS)
    {
        char[] SArr = pS.ToCharArray();

        if (pK > pS.Length * 4) {
            pK %= pS.Length * 4;
        }

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        var VisitedSet = new HashSet<long>();

        for (long I = 0; I <= SArr.GetUpperBound(0); I++) {
            WillPush.CurrNode = I + pK;
            WillPush.NodeVal = SArr[I];
            WillPush.Level = 1;
            Stk.Push(WillPush);

            VisitedSet.Add(I + pK);
        }

        bool IsOK = true;

        while (Stk.Count > 0) {
            if (IsOK == false) return false;

            JyoutaiDef Popped = Stk.Pop();

            long CurrNode = Popped.CurrNode;
            //Console.WriteLine("CurrNode={0},NodeVal={1},Level={2}",
            //    Popped.CurrNode, Popped.NodeVal, Popped.Level);

            Action<long> PushAct = (pNextNode) =>
            {
                //Console.WriteLine("{0}から{1}に遷移しました", Popped.CurrNode, pNextNode);

                // 中央区間の場合
                if (pK <= pNextNode && pNextNode <= pK + pS.Length - 1) {
                    char NextNodeVal = SArr[pNextNode - pK];
                    if (Popped.NodeVal != NextNodeVal) {
                        IsOK = false;
                        return;
                    }
                }
                if (VisitedSet.Add(pNextNode)) {
                    WillPush.CurrNode = pNextNode;
                    WillPush.NodeVal = Popped.NodeVal;
                    WillPush.Level = Popped.Level + 1;
                    Stk.Push(WillPush);
                }
            };

            // 左の区間の場合
            if (CurrNode <= pK - 1) {
                long UB1 = pK + pS.Length - 1;
                long PairInd1 = UB1 - CurrNode;
                PushAct(PairInd1);
                PushAct(pK + pS.Length + CurrNode);
            }

            // 中央区間の場合
            if (pK <= CurrNode && CurrNode <= pK + pS.Length - 1) {
                long UB1 = pK + pS.Length - 1;
                long PairInd1 = UB1 - CurrNode;
                PushAct(PairInd1);

                long UB2 = pK + pS.Length - 1;
                long PairInd2 = UB2 - (CurrNode - pK);
                PushAct(PairInd2 + pK);
            }

            // 右の区間の場合
            if (pK + pS.Length <= CurrNode) {
                long UB1 = pK + pS.Length - 1;
                long PairInd1 = UB1 - (CurrNode - pK);
                PushAct(PairInd1 + pK);
                PushAct(CurrNode - pS.Length - pK);
            }
        }

        return true;
    }
}

解説

KがSの4倍より長い場合は、
Sの4倍でmodを取ってます。
(考察すると、周期性があると分かるため)