禁止された数字

• 禁止された数字

解法

• dp[桁][A超える][B未満][4含む][9含む]のDPを書いた
• 「4を含む」と「9を含む」を1つにまとめてもいいっぽいけど、2つに分けた方が僕はわかりやすい。

コード

• いままでループでDPテーブル初期化してたけど今回はmemset使ってみた。memsetは罠があった気がするけど、-1で初期化するときは特に罠はなかった気がする。たぶん

#include <bits/stdc++.h>
using namespace std;

#define int long long

string A, B;
int dp[20][2][2][2][2]; // dp[桁][Aより大きい][B未満][４を含む][9を含む]

int rec(int digit, int moreA, int lessB, int four, int nine) {
  if (digit >= B.size()) {
    return four || nine;
  }

  if (dp[digit][moreA][lessB][four][nine] != -1) {
    return dp[digit][moreA][lessB][four][nine];
  }

  int high = (lessB ? 9 : B[digit] - '0');
  int low = (moreA ? 0 : A[digit] - '0');

  int ret = 0;
  for (int num = low; num <= high; num++) {
    int t = rec(digit + 1, moreA || num > low, lessB || num < high, four || (num == 4), nine || (num == 9));
    ret += t;
  }

  return dp[digit][moreA][lessB][four][nine] = ret;
}

signed main() {
  cin >> A >> B;
  // Aの足りない分を0で埋める
  int diff = B.size() - A.size();
  string zero = "";
  for (int i = 0; i < diff; i++) {
    zero += "0";
  }
  A = zero + A;

  memset(dp, -1, sizeof(dp));

  // 再帰に投げる
  int ans = rec(0, 0, 0, 0, 0);
  cout << ans << endl;

  return 0;
}

メモ

• トーラスさんの記事
• 「B以下の場合の数 - A未満の場合の数」がで求める方法もいいと思った。けど、桁数が多いと処理がめんどくさそう。A未満はAから1引いた数だけど、桁数が多いと1引く処理がちょっとだるそう（桁数多いと文字列で処理したりするから）。
• まあ、そういう考え方もあるという感じの認識で。