Python3で解く AtCoder Beginner Contest 152 D - Handstand 2
数値そのもので考えるというより、その数値の先頭とお尻の数値の組と逆にしたお尻と先頭の数値の組みがそれぞれ幾つ存在するのかっていうことを考える問題。こういう時はdefaultdict(というか常にdefaultdictでいいと思うけど)で行う。 dictでやる場合とdefaultdictでやる場合で何が違うのかを示してみる。
目次
概要
- が与えられる。
- 以下の正の整数の組について以下の条件を満たすものはいくつある?
- の一番右の桁の値がの一番左の桁の値と一致する。
- の一番左の桁の値がの一番右の桁の値と一致する。
- 例えばのとき、(1, 11)や(12, 21)は条件を満たしている。順列なので(11, 1)や(21, 12)は別カウントとして考える。
解くときに考えた内容
- 一緒になる数値がどのパターンがあるかというのを考えると煩雑になりすぎる。
- 例えば1, 11, 101・・・など。
- 以上以下の正の整数の組をすべてカウントする。
- その組の中に、入れ替えた以下の正の整数の組がいくつあるかを探索する。
- この時の以上以下における、の個数 の個数の和は?
- 実装上は数字を文字列として扱う方が一番右と一番左の値を取得するのが簡単。
keyの存在の有無によるdictとdefaultdictの違い
- コードを見が方がわかりやすいが、dictではkeyが存在しない時に処理しようとするとエラーになるため、if文でkeyがない時の処理を書く必要がある。
- defaultdictではその処理を書く必要がない。
コード
defaultdictを用いた場合
from collections import defaultdict n = int(input()) d = defaultdict(int) for i in range(1, n+1): s = str(i) # 一番左の数字 a = s[0] # 一番右の数字 b = s[-1] d[a, b] += 1 ans = 0 d_items = list(d.items()) for (a, b), v in d_items: ans += v * d[b,a] print(ans)
dictを用いた場合
n = int(input()) d = dict() for i in range(1, n+1): s = str(i) # 一番左の数字 a = s[0] # 一番右の数字 b = s[-1] # keyない時の処理が必須 if (a, b) not in d: d[(a, b)] = 0 d[(a, b)] += 1 ans = 0 d_items = list(d.items()) for (a, b), v in d_items: if (b, a) not in d: d[(b, a)] = 0 ans += v * d[(b, a)] print(ans)