ABC114 C問題

競プロ精進日記をつけていこうと思います。とは言っても、実力が全然ないので、かける内容もほとんどないのですが、しばらくは、解けなかった問題 and 解説見て真新しいと感じた内容 をブログという形で残していこうと考えています。

しばらくの間は振り返りしたい問題番号をKeepする目的がメインになるため、内容が薄いことにご理解いただきたいです。

今回の問題文へのリンクはこちら

atcoder.jp

問題文

整数 Nが与えられます。1以上 N以下の整数のうち、七五三数 は何個あるでしょうか？

ここで、七五三数とは以下の条件を満たす正の整数です。

十進法で表記したとき、数字 7, 5, 3 がそれぞれ 1回以上現れ、これら以外の数字は現れない。

制約

1 ≤ N < 10⁹( Nは整数である。)

考えたこと

1 ≤ N < 10⁹ を満たすN全てに対して全探索をすると 2msec の制限をオーバーする。

3, 5, 7だけで構成される数を全列挙したのちにそれぞれが一つ以上含まれるかの確認を行う。3,5,7 だけに限定することで、 3⁹ = 19683通りだけに限定することができ、制限時間内に実装することが可能である。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll n;
ll ans=0;

void dfs(ll x, int a, int b, int c) {
  if(x > n) return;
  if(a && b && c) ans++;
  dfs(10*x+3, 1, b, c);
  dfs(10*x+5, a, 1, c);
  dfs(10*x+7, a, b, 1);
}

int main() {
  cin >> n;
  dfs(0, 0, 0, 0);
  cout << ans << endl;

  return 0;
}