AtCoder Beginner Contest 152 D - Handstand 2

少し風邪をひいていました、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc)にて開催されました、AtCoder Beginner Contest 152 D問題「D - Handstand 2」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

正の整数 N が与えられます。 N 以下の正の整数の組 ( A , B ) であって、次の条件を満たすものの個数を求めてください。

• A , B を先頭に 0 のつかない 10 進数表記で表したときに、 A の末尾の桁が B の先頭の桁に等しく、 A の先頭の桁が B の末尾の桁に等しい

2.制約

• 1 ≤ N ≤ 2 × 10⁵
• 入力はすべて整数である。

3.入力例

• 入力

200000

• 出力

400000008

4.初見の感想

• 制約が2×10⁵であるのでO(N²)の計算量は難しい
• 最初と最後の文字を固定して、間の文字を再帰的に考える方法を最初考えた

→N以下という判定を行って個数を計算するところが少し複雑となる

→そもそも最初と最後の文字の組み合わせ分やらなければならない(9×9=81通り)

5.学びポイント

• O(N)の解法を考える
• 1~Nまでのfor文を回して数字をそれぞれ最初と最後の文字ごとに分類する
• 今回は二次元配列としてtemp[最初の文字,最後の文字]といった配列を用意し、それぞれの個数を分類しています
• 最初の文字の出し方→数字÷(10^桁数)で求められる(小数点以下切り下げ)
• 最後の文字の出し方→数字%10で求められる

6.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    static void Main(string[] args)
    {
        //入力
        int N = int.Parse(Console.ReadLine());
        int[,] temp = new int[10, 10];
        for (int i = 1; i <= N; i++)
        {
            //最初と最後の数字を出す
            int left = (int)(i / Math.Pow(10, (int)Math.Log10(i)));
            int right = (int)(i % 10);
            //数字を分類する
            if (left != 0 && right != 0)
            {
                temp[left, right]++;
            }
        }
        int ans = 0;
        for (int i = 0; i < 10; i++)
        {
            for (int j = 0; j < 10; j++)
            {
                //求めるパターンが何個か数える
                ans+=temp[i, j] * temp[j, i];
            }
        }
        Console.WriteLine(ans);
    }
}

7.最後に

この方針に行きつくまでに時間がかかってしまうのが反省点です…