AOJ 0674 桁和

問題へのリンク

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("13");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("20");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2019 ");
            //449
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int mN;
    static HashSet<int> mOKSet = new HashSet<int>();
    static HashSet<int> mNGSet = new HashSet<int>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        mN = int.Parse(InputList[0].Trim());

        for (int I = 1; I <= mN; I++) {
            if (mOKSet.Contains(I) || mNGSet.Contains(I)) {
                continue;
            }

            var VisitedSet = DeriveVisitedSet(I);
            if (VisitedSet.Contains(mN)) {
                mOKSet.UnionWith(VisitedSet);
            }
            else {
                mNGSet.UnionWith(VisitedSet);
            }
        }
        Console.WriteLine(mOKSet.Count);
    }

    static HashSet<int> DeriveVisitedSet(int pStaVal)
    {
        int CurrVal = pStaVal;
        var VisitedSet = new HashSet<int>();
        while (true) {
            if (CurrVal > mN) break;

            // 枝切りその1
            if (mOKSet.Contains(CurrVal)) {
                VisitedSet.Add(mN);
                break;
            }

            // 枝切りその2
            if (mNGSet.Contains(CurrVal)) break;

            VisitedSet.Add(CurrVal);
            CurrVal += GetKetaSum(CurrVal);
        }
        return VisitedSet;
    }

    // 数値を引数として、桁和を返す
    static int GetKetaSum(int pVal)
    {
        int WillReturn = 0;
        while (pVal > 0) {
            int Mod = pVal % 10;
            WillReturn += Mod;
            pVal /= 10;
        }
        return WillReturn;
    }
}

解説

枝切りを見落とさないDFSで解いてます。