ABC363-D Palindromic Number

問題へのリンク

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("46");
            //363
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1000000000000000000");
            //90000000000000000000000000000000009
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct InfoDef
    {
        internal decimal Cnt;
        internal decimal RunSum;
        internal decimal StaVal; // 回文の左半径の最小値
        internal decimal EndVal; // 回文の左半径の最大値
    }
    static Dictionary<decimal, InfoDef> mInfoDict = new Dictionary<decimal, InfoDef>();

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

        decimal CurrRunSum = 0;

        InfoDef FirstVal;
        FirstVal.Cnt = 10;
        FirstVal.StaVal = 0;
        FirstVal.EndVal = 9;
        CurrRunSum += FirstVal.Cnt;
        FirstVal.RunSum = CurrRunSum;
        mInfoDict[1] = FirstVal;

        InfoDef SecondVal;
        SecondVal.Cnt = 9;
        CurrRunSum += SecondVal.Cnt;
        SecondVal.RunSum = CurrRunSum;
        SecondVal.StaVal = 1;
        SecondVal.EndVal = 9;
        mInfoDict[2] = SecondVal;

        int CurrKeta = 3;
        while (true) {
            InfoDef CurrInfo;
            if (CurrKeta % 2 == 1) {
                decimal CurrStaVal = mInfoDict[CurrKeta - 1].StaVal * 10;
                decimal CurrEndVal = mInfoDict[CurrKeta - 1].EndVal * 10 + 9;
                CurrInfo.StaVal = CurrStaVal;
                CurrInfo.EndVal = CurrEndVal;
                CurrInfo.Cnt = CurrEndVal - CurrStaVal + 1;
                CurrRunSum += CurrInfo.Cnt;
                CurrInfo.RunSum = CurrRunSum;
                mInfoDict[CurrKeta] = CurrInfo;
            }
            else {
                CurrInfo.StaVal = mInfoDict[CurrKeta - 1].StaVal;
                CurrInfo.EndVal = mInfoDict[CurrKeta - 1].EndVal;
                CurrInfo.Cnt = CurrInfo.EndVal - CurrInfo.StaVal + 1;
                CurrRunSum += CurrInfo.Cnt;
                CurrInfo.RunSum = CurrRunSum;
                mInfoDict[CurrKeta] = CurrInfo;
            }
            if (mInfoDict[CurrKeta].RunSum >= N) break;
            CurrKeta++;
        }

        decimal RestCnt = N;

        foreach (var EachPair in mInfoDict) {
            //Console.WriteLine("桁数={0},Cnt={1},RunSum={2},StaVal={3},EndVal={4}",
            //    EachPair.Key, EachPair.Value.Cnt, EachPair.Value.RunSum,
            //    EachPair.Value.StaVal, EachPair.Value.EndVal);

            if (RestCnt - EachPair.Value.Cnt > 0) {
                RestCnt -= EachPair.Value.Cnt;
                continue;
            }
            decimal AnswerRadiusDec = EachPair.Value.StaVal + RestCnt - 1;
            string AnswerRadiusStr = AnswerRadiusDec.ToString();
            string RevStr = new string(AnswerRadiusStr.ToCharArray().Reverse().ToArray());
            if (EachPair.Key % 2 == 0) {
                Console.WriteLine(AnswerRadiusStr + RevStr);
            }
            else {
                Console.WriteLine(AnswerRadiusStr + RevStr.Substring(1));
            }
            break;
        }
    }
}

解説

紙とペンで考察すると、
回文の左半径を順に求めていけば良いと分かります。

オーバフロー対策でdecimal型を使用してます。