ABC101-D Snuke Numbers

問題へのリンク

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("10");
            //1
            //2
            //3
            //4
            //5
            //6
            //7
            //8
            //9
            //19
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct NumInfoDef
    {
        internal long Val;
        internal long KetaSum;
    }

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

        // 1から999に、末尾を9で埋めた数の、値と桁和を設定する
        var NumSet = new HashSet<long>();

        for (long I = 1; I <= 999; I++) {
            NumSet.Add(I);
            for (int J = 1; true; J++) {
                string NewStrNum = I.ToString() + new string('9', J);
                if (NewStrNum.Length > 17) break;
                NumSet.Add(long.Parse(NewStrNum));
            }
        }

        var NumInfoList = new List<NumInfoDef>();
        foreach (long EachLong in NumSet) {
            NumInfoDef WillAdd;
            WillAdd.Val = EachLong;
            WillAdd.KetaSum = DeriveKetaSum(EachLong);
            NumInfoList.Add(WillAdd);
        }

        NumInfoList.Sort((A, B) =>
        {
            decimal Sahen = (decimal)A.Val * B.KetaSum;
            decimal Uhen = (decimal)B.Val * A.KetaSum;

            if (Sahen != Uhen) {
                return Sahen.CompareTo(Uhen);
            }
            return A.Val.CompareTo(B.Val);
        });

        long MaxVal = long.MinValue;
        foreach (NumInfoDef EachNumInfo in NumInfoList) {
            if (MaxVal < EachNumInfo.Val) {
                MaxVal = EachNumInfo.Val;

                if (N > 0) {
                    Console.WriteLine(EachNumInfo.Val);
                    N--;
                }
            }
        }
    }

    // 桁和を求める
    static long DeriveKetaSum(long pVal)
    {
        long WillReturn = 0;
        while (pVal > 0) {
            WillReturn += pVal % 10;
            pVal /= 10;
        }
        return WillReturn;
    }
}

解説

実験すると
末尾が9の数が条件を満たすと分かるので、
1から999までの数に対して
17桁を超えない範囲で
末尾に9を連続させた数を候補としてます。

値と桁和を使ってソートすれば、すぬけ数の判定はできます。