ABC380-D Strange Mirroring

問題へのリンク

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("aB");
            WillReturn.Add("16");
            WillReturn.Add("1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16");
            //a B A b A b a B A b a B a B A b
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("qWeRtYuIoP");
            WillReturn.Add("8");
            WillReturn.Add("1 1 2 3 5 8 13 21");
            //q q W e t I E Q
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("AnUoHrjhgfLMcDIpzxXmEWPwBZvbKqQuiJTtFSlkNGVReOYCdsay");
            WillReturn.Add("5");
            WillReturn.Add("1000000000000000000 123456789 1 987654321 999999999999999999");
            //K a A Z L
        }
        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();
    }

    struct RangeInfoDef
    {
        internal long Sta;
        internal long End;
    }
    static List<RangeInfoDef> mRangeInfoList = new List<RangeInfoDef>();

    static char[] mCharArr;

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

        mCharArr = InputList[0].ToCharArray();
        long[] KArr = GetSplitArr(InputList[2]);

        RangeInfoDef WillAdd;
        WillAdd.Sta = 1;
        WillAdd.End = mCharArr.Length;
        mRangeInfoList.Add(WillAdd);

        long KMax = KArr.Max();
        while (true) {
            long CurrSta = mRangeInfoList[mRangeInfoList.Count - 1].Sta;
            long CurrEnd = mRangeInfoList[mRangeInfoList.Count - 1].End;

            long NextSta = CurrEnd + 1;
            long NextEnd = NextSta + CurrEnd - 1;
            if (NextSta > KMax) break;

            WillAdd.Sta = NextSta;
            WillAdd.End = NextEnd;
            mRangeInfoList.Add(WillAdd);
        }

        var AnswerList = new List<char>();
        foreach (long EachK in KArr) {
            char Answer = Solve(EachK, false);
            AnswerList.Add(Answer);
        }
        Console.WriteLine(CharEnumJoin(" ", AnswerList));
    }

    // 解を返す
    static char Solve(long pCurrPos, bool pIsRev)
    {
        if (pCurrPos <= mRangeInfoList[0].End) {
            char Answer = mCharArr[pCurrPos - 1];
            if (pIsRev) {
                if ('a' <= Answer && Answer <= 'z') {
                    Answer = Answer.ToString().ToUpper()[0];
                }
                else {
                    Answer = Answer.ToString().ToLower()[0];
                }
            }
            return Answer;
        }

        foreach (RangeInfoDef EachRangeInfo in mRangeInfoList) {
            if (EachRangeInfo.Sta <= pCurrPos && pCurrPos <= EachRangeInfo.End) {
                long CurrLen = (long)(EachRangeInfo.End - EachRangeInfo.Sta + 1);
                return Solve(pCurrPos - CurrLen, pIsRev == false);
            }
        }
        throw new Exception();
    }

    // セパレータとChar型の列挙を引数として、結合したstringを返す
    static string CharEnumJoin(string pSeparater, IEnumerable<char> pEnum)
    {
        string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
        return string.Join(pSeparater, StrArr);
    }
}

解説

分かりやすく0と1で、初期値を0だけとして考えます。

0
0 1
0 1 1 0
0 1 1 0 1 0 0 1
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

セパレータと区間情報を追記します。
1    2    3 4    5 6 7 8    9 〜 16            17 〜 32
0 ■ 1 ■ 1 0 ■ 1 0 0 1 ■ 1 0 0 1 0 1 1 0 ■ 1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

よって、クエリごとに
区間開始が1なら、文字列にアクセスして解を求める。
区間開始が1超えなら、反転有無のbool値を逆転させてから、
反転元座標のクエリとし、
再帰で解くことができます。