けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 114 C - 755 (300 点)

現代の AtCoder では少ない、再帰関数を用いると良い感じに書ける全探索問題。
すごく教育的な問題!!!!!

問題へのリンク

問題概要

10 進法表記で各桁の値が 7 と 5 と 3 のみで、かつ 7, 5, 3 がすべて一度以上は登場するような数を「753 数」と呼ぶことにする。

整数  N が与えられて、 N 以下の 753 数が何個あるかを求めよ。

制約

  •  1 \le N \le 10^{9}

考えたこと

こういう問題が最近は少ない気がする。何も考えずにパッと再帰な全探索を書くスキルは超重要な気がする。ABC-C にはこういうのが増えてほしい気持ちがとてもある。

再帰関数を用いることで、以下のように 753 数を列挙して行く。そして  N を超えてしまったノードを打ち切って行く。列挙されるノード数は十分少ないので大丈夫1

f:id:drken1215:20190403124746p:plain

また同時に、「7 と 5 と 3 のうちのどれが登場したか」を表すビット再帰関数の引数に入れてしまうと実装しやすい。

#include <iostream>
using namespace std;

// 入力
long long N;

// cur: 現在の値、use: 7, 5, 3 のうちどれを使ったか, counter: 答え
void func(long long cur, int use, long long &counter){
    if (cur > N) return; // ベースケース
    if (use == 0b111) ++counter; // 答えを増やす

    // 7 を付け加える
    func(cur * 10 + 7, use | 0b001, counter);

    // 5 を付け加える
    func(cur * 10 + 5, use | 0b010, counter);

    // 3 を付け加える
    func(cur * 10 + 3, use | 0b100, counter);
}

int main() {
    cin >> N;
    long long res = 0;
    func(0, 0, res);
    cout << res << endl;
}

番外編

桁 DP でも解けて、その場合は  N \le 10^{18} とかでも解ける。


  1.  9 桁以内の「7 と 5 と 3 だけ」な数は  3^{9} + 3^{8} + \dots + 3^{0} 個しかなくて、これは十分小さい