ABC195-C Comma

問題へのリンク

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

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("1010");
            //11
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("27182818284590");
            //107730272137364
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        //場合の数[カンマの数,数字自由フラグ]なDP表
        long[,] PrevDP = new long[6, 2];
        PrevDP[0, 0] = 1;

        int UB = N.Length - 1;
        for (int I = 0; I <= UB; I++) {
            long[,] CurrDP = new long[6, 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 > '0') {
                            int RestKeta = UB - I;
                            int CommaCnt = RestKeta / 3;
                            NewJ = Math.Max(NewJ, CommaCnt);
                        }
                        int NewK = K;
                        if (N[I] > NewChar) NewK = 1;

                        CurrDP[NewJ, NewK] += PrevDP[J, K];
                    }
                }
            }
            //Console.WriteLine("{0}桁目のDP結果", I);
            //for (int J = 0; J <= PrevDP.GetUpperBound(0); J++) {
            //    for (int K = 0; K <= PrevDP.GetUpperBound(1); K++) {
            //        Console.WriteLine("CurrDP[{0},{1}]={2}", J, K, CurrDP[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);
    }
}

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("1010");
            //11
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("27182818284590");
            //107730272137364
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;

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

        long CommaCnt1 = DeriveCommaCnt(1000, 999999, 1);
        long CommaCnt2 = DeriveCommaCnt(1000000, 999999999, 2);
        long CommaCnt3 = DeriveCommaCnt(1000000000, 999999999999, 3);
        long CommaCnt4 = DeriveCommaCnt(1000000000000, 999999999999999, 4);
        long CommaCnt5 = DeriveCommaCnt(1000000000000000, 999999999999999999, 5);
        long Answer = CommaCnt1 + CommaCnt2 + CommaCnt3 + CommaCnt4 + CommaCnt5;
        Console.WriteLine(Answer);
    }

    // 範囲の開始と終了を引数として、Nに存在するカンマの数を返す
    static long DeriveCommaCnt(long pSta, long pEnd, long pCommaCnt)
    {
        if (mN < pSta) {
            return 0;
        }
        if (pSta <= mN && mN <= pEnd) {
            return (mN - pSta + 1) * pCommaCnt;
        }
        if (pEnd < mN) {
            return (pEnd - pSta + 1) * pCommaCnt;
        }
        return -1;
    }
}

解説

区間ごとのカンマの数を考えると

1から999 は 0個の区間
1000から999999 は 1個の区間
1000000から999999999 は 2個の区間
1000000000から999999999999 は 3個の区間

ですので、区間ごとに
●全く含まない
●一部を含む
●完全に含む
の3通りで場合分けして、解に計上してます。