AtCoder Beginner Contest 114 [C - 755]

コメント歓迎です。
コンテストに参加したので1問ずつ記事を分けて解答を載せていきます。

今回はC問題です。
コンテスト時間内に解くことができませんでした。

コードは意外に短く、プログラミングの面白さを再認識しました。

問題

abc114.contest.atcoder.jp

方針

この問題のポイントは2つあります。

1つ目は、どうやって3, 5, 7の数字のみで構成された複数桁の数値を作るかです。

2つ目は、どうやって作った複数桁の数値に3, 5, 7がひとつ以上含まれていることを判定するかです。

まず、3, 5, 7の数字のみで構成された複数桁の数値を作る方法について考えます。

もし3種類の数字でなく2種類の数字であればビット全探索で列挙できますが、
今回は3種類のため別の方法が必要となります。

結論としては回帰関数(深さ優先探索)を使います。

考え方のイメージとしては「3」と「5」と「7」のマスがあり、マスの進み方を全探索していきます。

今記録している数値をとすると、1マス進むたびにの処理をしていきます。

そうすると記録している数値は3575735553といった具合に3と5と7のみで構成された複数桁の数値を作ることができます。

問題の制約から、の値が入力Nの数値を超えた場合はそのdfsは終わるようにします。

dfsは再帰関数なので、1つdfsが終わってもそのdfsを呼び出したdfsの処理に戻ることに注意です。

次に作った数値に3, 5, 7がひとつ以上含まれているか判定することを考えます。

方法としてはdfsで「3」に進んだときはflag3をtrueにし、flag5, flag7は移動前の状態を引き継ぎます。
「5」や「7」についても同様にします。

そうすると、一度でも3に進めばflag3はtrueとなります。

flag5, flag7についてもどうようですので、flag3, flag5, flag7がすべてtrueであれば、
「3」, 「5」, 「7」がひとつ以上含まれていることが確認できます。

「3」, 「5」, 「7」がひとつ以上含まれている場合は条件を満たしますので、ansに+1してカウントします。

コード(AC)

#include <iostream>
using namespace std;
typedef long long ll;
  
int N;
int ans = 0;
  
// 3, 5, 7を組み合わせて作れる数値を全探索
void dfs(ll x, bool flag3, bool flag5, bool flag7) {
  if (x > N) return;
  // 3, 5, 7をすべて含むならansに+1
  if (flag3 && flag5 && flag7) ans++;
  
  dfs(10 * x + 3, true, flag5, flag7);
  dfs(10 * x + 5, flag3, true, flag7);
  dfs(10 * x + 7, flag3, flag5, true);
}
  
int main() {
  // 入力
  cin >> N;
  
  // 深さ優先探索
  dfs(0, 0, 0, 0);
  
  // 出力
  cout << ans << endl;
}