[AtCoder Beginner Contest 152-D問題]を解く！

記事の概要

今回解くのはABC152-D問題。最初問題を読んでも全く意味がわからず、解説を読んでも理解することに時間がかかった。今は理解しているが少し経てばどうせ忘れるので自分の考えをまとめておこうという魂胆である。

問題

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

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

[制約]
- 1≤N≤2×105
- 入力はすべて整数である。

[入力]
N

考え方

まず条件を見てみよう。数字の最初の一桁と最後の一桁を入れ替えたやつがペアになる(間は何だろうと関係ない)ということなので例えば(12,21)や(102,221)になる。少し特殊な例だと(1,1)や(1,11)もペアである。要するには最初の一桁(1~9)と最後の一桁(0~9)を管理して、同じものをひとまとめにすれば良い。例を挙げると(12,102,112,122,132)はどれも最初が1で最後が2なので区別する必要がないのである。なら二次元配列[最初の数字][最後の数字]で管理できると考えられる。

for(int i = 1 ; i <= n ; i++){
        int v = static_cast<int>(log10(i)); 
        int max = i / pow(10,v); //最初の一桁
        int min = i % 10;  //最後の一桁
        number[max][min]++;
    }

最後の一桁は10で割ればあまりで出てくるから簡単。最初の一桁は少しめんどくさくて、まずlogで桁数-1を求めて、10の桁数-1乗で割れば商で出てくる。二次元配列には最初の一桁と最後の一桁が同じ数字の個数がカウントされていく。
しかしこれではまだ答えになっていない。number[1][2]とnumber[2][1]をペアにしないといけない。Nを150と考えるとnumber[1][2]には(12,102,112,122,132,142)の6が格納されている。一方number[2][1]には(21,201,211,221,231,241)の6が格納されている。ペアの総数は組み合わせで出るので6*6=36ということになる。要するにnumber[max][min] * number[min][max]の総和である。

解答例

handstand2.cpp

    #include <bits/stdc++.h>
    using namespace std;

    int main(){
        int n,ans;
        cin >> n;
        int number[10][10];

        for(int i = 0 ; i < 10 ; i++){
            for(int j = 0 ; j < 10 ; j++){
                number[i][j] = 0;
            }
        }

        //最初の一桁と最後の一桁が同じ数字をひとまとめにして個数を格納
        for(int i = 1 ; i <= n ; i++){
            int v = static_cast<int>(log10(i)); //最初の一桁
            int max = i / pow(10,v); //桁数計算
            int min = i % 10; //最後の一桁
            number[min][max]++;
        }

        //ペアの総数計算
        for(int i = 0 ; i < 10 ; i++){
            for(int j = 0 ; j < 10 ; j++){
                ans += number[i][j] * number[j][i]; //組み合わせ
            }
        }

        cout << ans;
        return 0;
    }

最後に

書いている時はすごく考えがまとまっているけど、時間が経って読み直す時は何言ってんだこいつってなりそう。ちょっとしたら読み直して修正します。読んでくれたみなさんありがとう。