ABC152-D Handstand 2

問題へのリンク

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("25");
            //17
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1");
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("100");
            //108
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("2020");
            //40812
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("200000");
            //400000008
        }
        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]);

        // 件数[先頭桁*10 + 末尾の桁] なDict
        var CntDict = new Dictionary<long, long>();
        for (int I = 1; I <= N; I++) {
            long Mod10 = I % 10;
            long TopKeta = long.Parse(I.ToString().Substring(0, 1));

            long Hash = TopKeta * 10 + Mod10;
            if (CntDict.ContainsKey(Hash) == false) {
                CntDict[Hash] = 0;
            }
            CntDict[Hash]++;
        }

        long Answer = 0;
        foreach (var EachPair in CntDict) {
            long CurrHash = EachPair.Key;

            long GetHash = 10 * (CurrHash % 10) + CurrHash / 10;
            if (CntDict.ContainsKey(GetHash)) {
                Answer += EachPair.Value * CntDict[GetHash];
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

最初に、先頭桁と末尾桁ごとの件数をDictionaryに集計してます。
次に、積の法則と、和の法則を使って、解を求めてます。