ABC114 C問題 : 755

問題. 755

整数 が与えられる． 以上 以下の整数のうち，各桁が数字 '3', '5', '7' のいずれかで，かつ，'3', '5', '7' の数字が少なくとも1回以上現れるものの数を求めよ．

制約：

解法1. 全列挙

条件を満たす整数を再帰関数で全列挙します． の桁数は高々9なので全列挙をしても に比例する時間しかかかりません．

計算時間： （ は の桁数）

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n;
const array<int, 3> add = {3, 5, 7};

int Solve(ll x, char flag) {
    if (n < x) return 0;

    int res = (flag == 7);
    for (int i = 0; i < 3; ++i)
        res += Solve(10 * x + add[i], flag | (1 << i));
    return res;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    cin >> n;
    cout << Solve(0, 0) << endl;;

    return 0;
}

解法2. 桁DP

の桁数による動的計画法である桁DP（Digit DP）を行います．漸化式 dp[i][j][k][l] を，上位 桁目までの数字を決めていて，上位 桁目で数字を自由に選べるかどうかのフラグを として，現在までに数字を書き込んだかのフラグを として，今までで '3', '5', '7' を少なくとも1回選んだかどうかのフラグを としたときの，それを満たす整数の個数と定義します． の桁数を としたとき，答えは dp[s][0][1][7] + dp[s][1][1][7] となります．これは，すべての桁数を決めたときに，数字が書かれており，'3', '5', '7' が少なくとも1回書かれているときの数となります．漸化式はソースコードを参照してください．

計算時間： （ は の桁数）

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

// dp[i][j][k][l] := i: 上位 i 桁目まで決定，j: 数字を自由に選べるか,
//                   k: 数字を書き込んだか，l: {3,5,7} を選んだかのflag
//                   としたときの753数の数
int dp[11][2][2][8];

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    string n;
    cin >> n;

    int len = n.size();
    dp[0][0][0][0] = 1;
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                for (int l = 0; l < 8; ++l) {
                    if (!dp[i][j][k][l]) continue;

                    if (j == 1) { // [0, 9] から数字を選べる
                        if (k == 0) // 数字をまだ書き込んでいない
                            dp[i + 1][1][0][0] += dp[i][j][k][l]; // nothing

                        dp[i + 1][1][1][l | 1] += dp[i][j][k][l]; // +3
                        dp[i + 1][1][1][l | 2] += dp[i][j][k][l]; // +5
                        dp[i + 1][1][1][l | 4] += dp[i][j][k][l]; // +7
                    }
                    else { // [0, d] から数字を選べる
                        int d = (int)(n[i] - '0');

                        if (k == 0) // 数字をまだ書き込んでいない
                            dp[i + 1][1][0][0] += dp[i][j][k][l]; // nothing

                        if (d == 3) dp[i + 1][0][1][l | 1] += dp[i][j][k][l]; // +3
                        if (3 < d) dp[i + 1][1][1][l | 1] += dp[i][j][k][l]; // +3
                        if (d == 5) dp[i + 1][0][1][l | 2] += dp[i][j][k][l]; // +5
                        if (5 < d) dp[i + 1][1][1][l | 2] += dp[i][j][k][l]; // +5
                        if (d == 7) dp[i + 1][0][1][l | 4] += dp[i][j][k][l]; // +7
                        if (7 < d) dp[i + 1][1][1][l | 4] += dp[i][j][k][l]; // +7
                    }
                }
            }
        }
    }

    int ans = dp[len][0][1][7] + dp[len][1][1][7];
    cout << ans << endl;

    return 0;
}

まとめ

桁DP はなかなか思考に時間がかかるな．あとパラメータが増えると vector<vector<vector<vector<int>>>> となって険しい．