AtCoder Beginner Contest 114 C - 755

beta.atcoder.jp

問題概要

1以上N以下の整数で、「十進法で表記したとき、数字7, 5, 3がそれぞれ1回以上現れ、これら以外の数字は現れない」ものはいくつあるか？
1 <= N < 10^9

解法

入力例3が最大のN（=99999999）で、このときの答えが26484だから、全部作れそう。
itertoolsのproduct（直積）でrepeat = kとすると、k個の["3","5","7"]から1個ずつ要素を取り出してきてできるセットのリストが作れる。

例えば list(itertools.product(["3","5","7"], repeat=2)) （これはlist(itertools.product(["3","5","7"],["3","5","7"]))と同じ）だと
[('3', '3'), ('3', '5'), ('3', '7'), ('5', '3'), ('5', '5'), ('5', '7'), ('7', '3'), ('7', '5'), ('7', '7')]になる。

これを使って3回以上Nの桁数回以下だけ["3","5","7"]から要素を取り出してきて、3,5,7が一つ以上入っていればくっつけてintに変換してLに加える。
あとはLをソートして、Nが挿入できる位置を答えにする。

# ABC 114 C
import itertools, bisect
N = int(input())
d = len(str(N))

L =  []
for k in range(3,d+1):
    for a in itertools.product(["3","5","7"], repeat=k):
        if "3" in a and "5" in a and "7" in a:
            L.append(int("".join(a)))

L = sorted(L)
print(bisect.bisect_right(L, N))