ABC114 C - 755

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import collections
import itertools
import heapq

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = iss()
    S = []
    for i in range(1, 10):
        S += set(itertools.product('753', repeat=i))
    ret = 0
    for s in S:
        if '7' in s and '5' in s and '3' in s and int(N) >= int("".join(s)):
            ret += 1
    print(ret)


if __name__ == '__main__':
    main()

考え方

先に7, 5, 3のみで構成される1桁から9桁までの数値を全て生成しておき、
条件に一致する値をカウントする。
7, 5, 3のみで構成される1桁から9桁までの数値を全て生成しても、
3 * 10 ** 5個程度なので、処理時間も余裕で間に合う。

数値の生成にはデカルト積(itertools.product)を使用する。
productは引数に使用する文字列、repeatで繰り返し回数をとる。
今回、文字列には7, 5, 3を使用し、
繰り返し回数はrange(1, 10)で指定することで、1桁から9桁まで生成した。