ARC144-A Digit Sum of 2x

問題へのリンク

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("3");
            //6
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6");
            //12
            //24
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("100");
            //200
            //4444444444444444444444444
        }
        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]);
        long M = N * 2;

        var sb = new System.Text.StringBuilder();
        long Rest = N;
        while (Rest > 0) {
            if (Rest >= 4) { sb.Append(4); Rest -= 4; continue; }
            if (Rest >= 3) { sb.Append(3); Rest -= 3; continue; }
            if (Rest >= 2) { sb.Append(2); Rest -= 2; continue; }
            if (Rest >= 1) { sb.Append(1); Rest -= 1; continue; }
        }
        Console.WriteLine(M);

        string RevStr = new string(sb.ToString().ToCharArray().Reverse().ToArray());
        Console.WriteLine(RevStr);
    }
}

解説

f(X) = Xの各桁の数字の和
で、
f(x) = N かつ
f(2x) = M
である、最大のM
になるxを考えます。

xの各桁について考えると
1の場合は、2倍したら2で桁和への計上は2
2の場合は、2倍したら4で桁和への計上は4
3の場合は、2倍したら6で桁和への計上は6
4の場合は、2倍したら8で桁和への計上は8
5の場合は、2倍したら10で桁和への計上は1
6の場合は、2倍したら12で桁和への計上は3
7の場合は、2倍したら14で桁和への計上は5
8の場合は、2倍したら16で桁和への計上は7
9の場合は、2倍したら18で桁和への計上は9

よって、
Mを最大にするときのxは、1のみで構成すれば良いと分かりので、
M = 2 * N
になります。

次に
f(x) = N かつ
f(2x) = 2 * N
の中で最小のxですが
これは、4,3,2,1の順で貪欲に数字を選択してから
逆に並べれば良いです。