AtCoder Beginner Contest 114 / C - 755

Reiwa一発目から解説ACで悔しい(ﾋﾞｸﾝﾋﾞｸﾝ

方針は以下。

1. 制約条件のため、1~Nの全件調査は間に合わない。

2. '753'のいずれかを含む値を 準753数 と定義して、これを全列挙する。

   • 停止条件：sが入力Nに達すること
   • 動作1：まず現在与えられている値の753数判定をする。
   • 動作2：その後、その結果とは関係なく、今の桁数+1の753数を作ってdfs。
3. 優勝

def dfs(s :str, n: int):
    if(int(s) > n):
        return 0
    ret = 1 if all(s.count(c) for c in '753') else 0
    for c in '753':
        ret += dfs(s+c, n)
    return ret


def solve(N: int):
     # 0を入れないと、if(int(s) > n)で引掛かる
    print(dfs('0',N))