ABC 桁DP atcoder

ABC007 D - 禁止された文字

ABC007 D - 禁止された文字の解説です。桁DPを使用します。
Feb. 22, 2020, 6:44 a.m.

目次

問題

https://atcoder.jp/contests/abc007/tasks/abc007_4

$4$と$9$をいずれも含まない整数の数を求める問題です。

入力

A B
  • $A$以上$B$以下のうち条件を満たす整数をカウントします。( $1 \leq A \leq B \leq 10^{18}$ )

出力

N
  • N - 条件を満たす整数の数

入出力例

1 1000
488

解説

TODO

計算量

TODO

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
Int AA, BB;
vector<int> A, B;
#define MOD 1000000007

void input() {
  Int A_, B_;
  cin >> A_ >> B_;
  AA = A_, BB = B_;
  A_--;

  while (A_ > 0) {
    A.push_back(A_ % 10);
    A_ = (A_ / 10);
  }
  reverse(span_all(A));

  while (B_ > 0) {
    B.push_back(B_ % 10);
    B_ = (B_ / 10);
  }
  reverse(span_all(B));
}

// (整数の最大桁数, 次の数字に制限があるか)
Int dp[20][2];

Int solveRec(vector<int> &digits, Int k = 0, bool tight = true) {
  // 整数文字列の最後まで到達
  if (k == digits.size()) {
    return 1;
  }
  Int x = digits.at(k);
  Int r = tight ? x : 9; // その桁において最大の場合は次の桁で制限がかかる

  Int res = dp[k][tight];
  if (~res) return res; // DP
  res = 0;
  for (Int i=0; i<=r; i++) {
    if (i == 4 || i == 9) continue;
    res += solveRec(digits, k + 1, tight && i == r);
  }
  dp[k][tight] = res;
  return res;
}

void solve() {
  memset(dp, -1, sizeof(dp));
  Int total = solveRec(B);
  memset(dp, -1, sizeof(dp));
  total -= solveRec(A);
  cout << BB - AA + 1 - total << endl;
}

int main() {
  input();
  solve();
  return 0;
}