ABC152 D - Handstand 2
問題原文
問題要旨
以下の正の整数の組 であって、 の末尾の桁が の先頭の桁に等しく、 の先頭の桁が の末尾に等しいようなものの個数を求めよ。
解法
とすると、 となる。(x
は存在しないこともある)
じゃあ を固定して、とりうる間のパターンを数えよう。。。→地獄実装のはじまり\(^0^)/
ここで一度立ち止まって、「先頭が5で末尾が1であるような数はいくつあるか?」 と考える。
これは を1からなめていけば容易に数えられる。
もっと言えば、 先頭が で、末尾が であるような数の個数 は前計算できる!
よって、 として、 が答えになる。
実装
N = int(input()) # cnt[i][j] := 先頭がi, 末尾がjで始まるような数 cnt = [[0] * 10 for i in range(10)] for n in range(1, N + 1): cnt[int(str(n)[0])][int(str(n)[-1])] += 1 ans = 0 for i in range(10): for j in range(10): ans += cnt[i][j] * cnt[j][i] print(ans)
感想
詰めたと思っても、もっと詰められるかも?という意識を忘れないように。。。。
ABC-Dで筋肉実装なんてそうそう出ないんですよ。。。。反省します