第5回PAST J 長い長い文字列

問題へのリンク

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("ab2c1");
            WillReturn.Add("6");
            //b
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("atcoder");
            WillReturn.Add("6");
            //e
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("a999999999999999");
            WillReturn.Add("1000000000000000");
            //a
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct TotalLenInfoDef
    {
        internal char CurrChar;
        internal long TotalLen;
    }

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

        var TotalLenInfoList = new List<TotalLenInfoDef>();
        foreach (char EachChar in S) {

            TotalLenInfoDef WillAdd;
            WillAdd.CurrChar = EachChar;

            if ('1' <= EachChar && EachChar <= '9') {
                if (TotalLenInfoList.Count > 0) {
                    int CurrNum = EachChar - '0';
                    WillAdd.TotalLen = TotalLenInfoList.Last().TotalLen * (1 + CurrNum);
                }
                else {
                    WillAdd.TotalLen = 0;
                }
            }
            else {
                if (TotalLenInfoList.Count > 0) {
                    WillAdd.TotalLen = TotalLenInfoList.Last().TotalLen + 1;
                }
                else {
                    WillAdd.TotalLen = 1;
                }
            }
            TotalLenInfoList.Add(WillAdd);

            if (WillAdd.TotalLen >= X) break;
        }

        while (true) {
            for (int I = 0; I <= TotalLenInfoList.Count - 1; I++) {
                TotalLenInfoDef CurrTotalLenInfo = TotalLenInfoList[I];
                char CurrChar = CurrTotalLenInfo.CurrChar;
                if ('a' <= CurrChar && CurrChar <= 'z') {
                    if (CurrTotalLenInfo.TotalLen == X) {
                        Console.WriteLine(CurrChar);
                        return;
                    }
                }
                else if (CurrTotalLenInfo.TotalLen >= X) {
                    // 1つ前の長さが周期になる
                    long PrevTotalLen = TotalLenInfoList[I - 1].TotalLen;
                    X %= PrevTotalLen;
                    if (X == 0) X = PrevTotalLen;
                    break;
                }
            }
        }
    }
}

解説

ab2c1
という入力を考えると下記の表になります。

  トータル文字数
a  1
b  2
2  6
c  7
1 14

X文字目が知りたいので、
aからzでトータル文字数とXが一致した場合は、解として確定です。
1から9でトータル文字数がX以上だったら、
X %= (1つ上のトータル文字数)
ただし、Xが0になったら、 X = (1つ前のトータル文字数)
とします。

するとXが減っていき、解が求まります。