ABC-029-D 1

■■■問題■■■

高橋君は1以上N以下のすべての整数を十進表記で1回ずつ紙に書きました。
この作業で、高橋君は1という数字を何個書いたでしょうか。

■■■入力■■■

N

1行目に整数 N (1 <= N < 10億) が与えられる。

■■■出力■■■

標準出力に、高橋君が書いた1という数字の個数を出力し、最後に改行せよ。

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("12");
            //5
            //1,10,11,12の十進表記に合計で5個の1という数字が含まれます
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("345");
            //175
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("999999999");
            //900000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        //for (int I = 1; I <= 20000; I++) {
        //    int Result1 = DervieCnt1(I);
        //    int Result2 = DervieCnt1Naive(I);

        //    Console.WriteLine("{0}までの1の数は{1}", I, Result1);
        //    Console.WriteLine("{0}までの1の数は{1}(ナイーブ版)", I, Result2);
        //    if (Result1 != Result2) {
        //        break;
        //    }
        //}
    }

    //1の数を求める
    static int DervieCnt1(int pLimit)
    {
        int WillReturn = 0;

        //上限の桁数を求める
        int LimitKetasuu = (int)Math.Truncate(Math.Log10(pLimit)) + 1;

        int Kousuu = pLimit + 1;

        //桁数のループ
        //1桁目は、{0123456789}の群数列
        //2桁目は、{0が10個、1が10個、2が10個、以下9まで}の群数列
        //3桁目は、{0が100個、1が100個、2が100個、以下9まで}の群数列
        for (int I = 1; I <= LimitKetasuu; I++) {
            int GunKousuu = (int)Math.Pow(10, I);
            int GunKousuuDev10 = GunKousuu / 10;

            //完全に含む群の数 * 群の中の1の数
            int wkCnt1 = Kousuu / GunKousuu * GunKousuuDev10;

            //完全に含まない群の中の1の数
            int wkCnt2;
            if (Kousuu % GunKousuu <= GunKousuuDev10) wkCnt2 = 0;
            else wkCnt2 = Math.Min(GunKousuuDev10, Kousuu % GunKousuu - GunKousuuDev10);

            WillReturn += wkCnt1 + wkCnt2;
        }

        return WillReturn;
    }

    //1の数を求める(ナイーブ版)
    static int DervieCnt1Naive(int pLimit)
    {
        int WillReturn = 0;
        for (int I = 1; I <= pLimit; I++) {
            int CopiedVal = I;
            while (CopiedVal > 0) {
                if (CopiedVal % 10 == 1) WillReturn++;
                CopiedVal /= 10;
            }
        }
        return WillReturn;
    }
}

C#のソース (桁DPを使う方法)

using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("12");
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("345");
            //175
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("999999999");
            //900000000
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        //場合の数[1の数,数字自由フラグ]なDP表
        int[,] PrevDP = new int[11, 2];
        PrevDP[0, 0] = 1;

        for (int I = 0; I <= N.Length - 1; I++) {
            int[,] CurrDP = new int[11, 2];

            for (int J = 0; J <= PrevDP.GetUpperBound(0); J++) {
                for (int K = 0; K <= PrevDP.GetUpperBound(1); K++) {
                    if (PrevDP[J, K] == 0) continue;

                    for (char NewChar = '0'; NewChar <= '9'; NewChar++) {
                        if (K == 0 && N[I] < NewChar) break;

                        int NewJ = J;
                        if (NewChar == '1') NewJ++;

                        int NewK = K;
                        if (N[I] > NewChar) NewK = 1;

                        CurrDP[NewJ, NewK] += PrevDP[J, K];
                    }
                }
            }
            PrevDP = CurrDP;
        }

        long Answer = 0;
        for (int I = 0; I <= PrevDP.GetUpperBound(0); I++) {
            for (int J = 0; J <= PrevDP.GetUpperBound(1); J++) {
                Answer += PrevDP[I, J] * I;
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

下記の昇順に並べた数値を桁ごとに縦方向に見た数列を、
群数列として考えてます。

0000
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
0018
0019
0020
0021
0022
0023
0024
0025
以下略