ABC114 C – 755

はじめに

競プロの精進のために学びがあった問題についてまとめています。
目標は AtCoder 水色！

今のレートは茶色です。

問題

ABC114 C – 755を解きました。

整数 N が与えられます。
1 以上 N 以下の整数のうち、七五三数 は何個あるでしょうか？
ここで、七五三数とは以下の条件を満たす正の整数です。
十進法で表記したとき、数字 7, 5, 3 がそれぞれ 1 回以上現れ、これら以外の数字は現れない。

難易度は緑色。

考察

全探索は当然間に合わないので、効率的に753数の条件を満たす数を洗い出したい。

ここで、753数の各桁の取りうる値は(7, 5, 3)のいずれかであるため、N以下の値のすべての桁に対して(7, 5, 3)の値を代入した数をカウントすればよい。

Nの最大値は10^9であるため、上記の網羅のためにはO(3^10)があればよく、これは59049であるため、計算時間に間に合う。

網羅のための実装には再帰関数を利用する。

ここで、753数の完成のためには3桁以上の整数が必要である点を考慮する必要がある。

コード

N = int(input())

def calc(n, k):
    t = pow(10,k)
    if n > N:
        return

    if k > 2:
        d = {}
        for c in str(n):
            if c == "3":
                d[c] = 1
            if c == "5":
                d[c] = 1

            if c == "7":
                d[c] = 1

        if len(d) == 3:
            global ans
            ans += 1

    for i in (3, 5, 7):
        a = t*i + n
        calc(a, k+1)

    return

ans = 0
for i in (3, 5, 7):
    calc(i, 1)

print(ans)

まとめ

Diffは緑上位ですが、僕でも10分くらいで解けたので今のレベルで言うところの茶Diff下位くらいな感じですね。

生成した数が753数かの判定はDictを使ったのですが、もっさりした実装なので何かもっと上手いやり方がありそうです。