ARC229-A AtCoder Reverse Contest

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            //ARARC
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("0");
            //ATCODER
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            //ARARCDARC
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long X = long.Parse(InputList[0]);

        // 625での解を求める
        string BaseStr = new string('A', 25) + new string('C', 25);
        BaseStr = Regex.Replace(BaseStr, "(?<=.)(?=.)", "R");

        var AnswerDict = new Dictionary<long, string>();
        AnswerDict[625] = BaseStr;

        for (long I = 624; 0 <= I; I--) {
            // ARCをCRAにReplace(1箇所のみ)
            BaseStr = StringReplace.StringReplaceUsingString(BaseStr, "ARC", "CRA", 1);

            AnswerDict[I] = BaseStr;
        }

        Console.WriteLine(AnswerDict[X]);
    }
}

#region StringReplace
// replace関数で回数指定できる静的クラス
internal class StringReplace
{
    // 正規表現版
    // 引数1 対象文字列
    // 引数2 検索する文字列
    // 引数3 置換する文字列
    // 引数4 置換回数
    static internal string StringReplaceUsingRegex(string pBase,
        string pPattern, string pReplace, long pCnt)
    {
        var InsRegex = new System.Text.RegularExpressions.Regex(pPattern);
        string Result = InsRegex.Replace(pBase, pReplace, (int)pCnt);
        return Result;
    }

    // 正規表現を使用しないString版
    // 引数1 対象文字列
    // 引数2 検索する文字列
    // 引数3 置換する文字列
    // 引数4 置換回数
    static internal string StringReplaceUsingString(string pBase,
        string pSearch, string pReplace, long pCnt)
    {
        var sb = new System.Text.StringBuilder();

        int UB = pBase.Length - 1;
        int CurrInd = 0;

        while (pCnt > 0 && CurrInd <= UB) {
            int ResultInd = pBase.IndexOf(pSearch, CurrInd);
            if (ResultInd < 0) break;

            for (int I = CurrInd; I <= ResultInd - 1; I++) {
                sb.Append(pBase[I]);
            }
            sb.Append(pReplace);
            CurrInd = ResultInd + pSearch.Length;
            pCnt--;
        }

        for (int I = CurrInd; I <= UB; I++) {
            sb.Append(pBase[I]);
        }
        return sb.ToString();
    }

    // 正規表現を使用しないChar版
    // 引数1 対象文字列
    // 引数2 検索する文字
    // 引数3 置換する文字
    // 引数4 置換回数
    static internal string StringReplaceUsingChar(string pBase,
        char pSearch, char pReplace, long pCnt)
    {
        var sb = new System.Text.StringBuilder();
        foreach (char EachChar in pBase) {
            if (pCnt > 0 && EachChar == pSearch) {
                sb.Append(pReplace);
                pCnt--;
            }
            else {
                sb.Append(EachChar);
            }
        }
        return sb.ToString();
    }
}
#endregion

解説

まず、問題を簡易化し
ACをCAにReplaceできると考えます。

すると
ACCCは、3回
AACCCは、6回
AAAACCは、8回
すなわち、Cごとに左のAの数だけReplaceを行うことができます。

最大で600回のReplaceが必要で、まずは
600回を実現する方法を考えます。

600のルートは、約24.49なので
Cを25個並べ、Aを25個並べる。
Rは間に入れるので、Rは49個必要で、
これは100文字の制限を満たします。
そして、この文字列でのReplace回数は625回です。

624回以下の文字列は、
625回の文字列に対し、ARCをRCAにreplaceをシュミレーションした結果を使えば良いです。