D - Handstand 2

[hxrxchang]

https://atcoder.jp/contests/abc152/tasks/abc152_d

問題概要

1 <= A, B <= N で、Aの末尾一桁とBの先頭一桁が同じでありかつ、Aの先頭一桁とBの末尾一桁が同じになる(A, B) の組み合わせの数を求めよ。 (1, 1), (12, 21), (42, 24) とかが該当する。

解き方

例えば、Aを123とする。するとBの候補は先頭3, 末尾1 の数字であるから、組み合わせ数は 1 <= i <= N までの数字で該当する個数が分かれば組み合わせ数がわかる。 よって、以下の方法で組み合わせ数がわかる。

1. 1 <= i <= Nの間で先頭が[i]末尾が[j]で終わる数の個数を事前に求めておく
2. 先頭が 1 <= i <= 9 末尾が 1 <= j <= 9 になる組み合わせ数を求めて合計する

これは自力で思いつきたかった...

func solve() {
    n := getInt()

    // cnt[i][j]: iで始まりjで終わる数の個数
    cnt := make([][]int, 10)
    for i := 0; i < 10; i++ {
        cnt[i] = make([]int, 10)
    }

    for i := 1; i <= n; i++ {
        s := strToSlice(i2s(i), "")
        start := s2i(s[0])
        end := s2i(s[len(s)-1])
        cnt[start][end] += 1
    }

    ans := 0
    for i := 1; i <= 9; i++ {
        for j := 1; j <= 9; j++ {
            ans += cnt[i][j] * cnt[j][i]
        }
    }

    fmt.Println(ans)
}

https://atcoder.jp/contests/abc152/submissions/53477650