ABC171-C One Quadrillion and One Dalmatians

問題へのリンク

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");
            //b
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("27");
            //aa
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("123456789");
            //jjddja
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        long N = long.Parse(InputList[0]);

        Solve(N);
    }

    static void Solve(long pN)
    {
        // 文字数ごとの場合の数を求める
        var StrPatternCntDict = new Dictionary<int, long>();
        long StrPatternCnt = 1;
        long RumSum = 0;
        for (int I = 1; I < int.MaxValue; I++) {
            StrPatternCnt *= 26;
            StrPatternCntDict[I] = StrPatternCnt;
            RumSum += StrPatternCnt;

            if (pN <= RumSum) break;
        }

        // 全体でN項目の文字列が、その文字数の群数列の何番目かを求める
        long PrevRumSum = 0;
        int[] KeysArr = StrPatternCntDict.Keys.ToArray();
        Array.Sort(KeysArr);
        for (int I = 0; I <= KeysArr.GetUpperBound(0) - 1; I++) {
            PrevRumSum += StrPatternCntDict[KeysArr[I]];
        }

        // その文字数の群数列の番目
        long TargetBanme = pN - PrevRumSum;

        string Answer = DeriveAnswer(TargetBanme, KeysArr.Max());
        Console.WriteLine(Answer);
    }

    // 群数列の番目と、何文字の群数列かを引数として、解を返す
    static string DeriveAnswer(long pBanme, long pKetaSuu)
    {
        long CurrVal = pBanme - 1;

        var CharList = new List<char>();
        do {
            long ModVal = CurrVal % 26;
            CharList.Add((char)('a' + ModVal));
            CurrVal /= 26;
        } while (CurrVal > 0);

        CharList.Reverse();
        string wkStr = new string(CharList.ToArray());
        wkStr = wkStr.PadLeft((int)pKetaSuu, 'a');
        return wkStr;
    }
}

解説

1文字の群数列
2文字の群数列
3文字の群数列
といった数列になってるとして、
最初に、どの群数列に所属しているかを求めて、
次に、群数列の番目に対応する26進数として求めてます。