ABC 114 Cを桁DPでも解いてみた
「桁DPで解きたくなる誘惑に負けず全探索で解くべき問題」ABC 114 Cを、後学のために桁DPでも解いてみたメモ。
(本番では3,5,7のみで出来た9桁までの数を全列挙しました)
桁DPのアイデアと実装については桁DP入門 - pekempey's blog がとても参考になります。
で
状態はどう持てばいいか
- 何桁目まで見たか ()
- N未満か (0..1)
- 3を既に含んでいるか (0..1)
- 5を既に含んでいるか (0..1)
- 7を既に含んでいるか (0..1)
- 357以外を含んでいるか (0..1)
- 0より大きいか (0..1)
「0より大きいか」というか、leading zeroを非753数字としてカウントしないフラグが必要。。(これに気づかなくてちょっと時間かかった。本番でやったらはまってただろう)
→AC
https://beta.atcoder.jp/contests/abc114/submissions/3711407
#include <bits/stdc++.h> using namespace std; #define rep(var, n) for (int var = 0; var < (n); ++var) vector<int> num_to_vec(int x, int base = 10) { if (x == 0) return vector<int>{0}; vector<int> v; while (x) { int q = x / base, r = x % base; v.push_back(r); x = q; } reverse(v.begin(), v.end()); return v; } int solve(int N) { vector<int> a = num_to_vec(N, 10); int K = a.size(); int dp[K + 1][2][2][2][2][2][2]; mset(dp, 0); dp[0][0][0][0][0][0][0] = 1; rep(i, K) rep(j, 2) rep(k, 2) rep(l, 2) rep(m, 2) rep(n, 2) rep(o, 2) { int lim = j ? 9 : a[i]; rep(d, lim + 1) { bool non357 = n ? (d != 3 && d != 5 && d != 7) : (d != 0 && d != 3 && d != 5 && d != 7); dp[i + 1][j || d < lim][k || d == 7][l || d == 5][m || d == 3][n || d][o || non357] += dp[i][j][k][l][m][n][o]; } } int ans = 0; rep(j, 2) rep(k, 2) rep(l, 2) rep(m, 2) rep(n, 2) rep(o, 2) { if (k == 1 && l == 1 && m == 1 && o == 0) ans += dp[K][j][k][l][m][n][o]; } return ans; } int main() { int N; cin >> N; cout << solve(N) << endl; return 0; }