[AtCoder] ABC 007 D – 禁止された数字

2019年8月23日

問題

方針

桁DP

\( n \) 以下の数字の中で \( 4 \) または \( 9 \) を含まない数の個数を求めます。\( d_{i, 0} \) を上位 \( i \) 桁目まで調べたとき、\( 4 \) または \( 9 \) を含むか含まないかのフラグとします。含まないときは、\( d_{i, 0} = 1 \) とし、含むときは、\( d_{i, 0} = 0 \) とします。また、\( d_{i, 1} \) を \( n \) 上位 \( i \) 桁まで調べた時、\( n \) の \( i \) 桁目までの数よりも小さい数で、\( 4 \) または \( 9 \) を含まない数の個数とします。このとき、\( n \) の桁数を \( l \) とすると、\( d_{l, 0} + d_{l, 1} \) が答えになります。\( d_{l, 0} = 1 \) となることに注意します。また、初期値として、\( d_{0, 0} = 1 \) とします。

ここで、\( n \) の \( i \) 桁目の数字を \( s_i \) とします。\( d_{i, 0} \) について、上位の桁から見て \( 4 \) または \( 9 \) が出現しない限り \( d_{i, 0} = 1 \) となります。出現した場合、その桁以降は \( d_{i, 0} = 0 \) となります。次に、\( d_{i, 1} \) について、\( 0 \leq j < s[i]  \wedge j \neq 4 \) を満たす \( j \) の個数を \( k \) とすると、

\[d_{i + 1, 1} = k \times d_{i, 0} + 8 \times d_{i, 1}\]

となります。

例えば、\( n = 8341 \) とすると、\( d_{i, 0} = 1 \ (0 \leq i \leq 2)\), \( d_{i, 0} = 0 \ (3 \leq i \leq 4)\) となります。\( d_{0, 1} = 0 \) として、上から \( 1 \) 桁目の数字は \(s_{1} =  8 \) なので、\( 8000 \) 未満の数字で、\( s_{1} \) の候補は、 \( (0, 1, 2, 3, 5, 6, 7)\) となるので、\( k = 7 \) より、\( d_{1, 1} = 7 + 8 \times 0\) となります。

次に、\( d_{2, 1} \) について考えます。同様にして、\( 8300\) 未満の数字で \( 8x?? \) の \( x \) に入る数字は \( (0, 1, 2) \) なので、\( k = 3\) となります。 また、\( xy?? \) ,  \( 0 \leq x \leq 7 \) という形で、\( y \) に入る数字は任意の数字となります。 以下同様にして最後の桁まで調べます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
// 0 ~ n で 4 と 9 を含まない個数
ll func(ll n) {
  string s = to_string(n);
  int l = s.length();
  ll dp[l + 1][2]{};
  dp[0][0] = 1;
  for (int i = 0; i < l; i++) {
    ll k = 0;
    for (int j = 0; j < 9; j++) {
      if (j == 4) continue;
      if (j < s[i] - '0') k++;
    }
    
    if (s[i] == '4' || s[i] == '9') {
      dp[i + 1][0] = 0;
    } else {
      dp[i + 1][0] = dp[i][0];
    }
    dp[i + 1][1] = k * dp[i][0] + 8 * dp[i][1];
  }
  return dp[l][0] + dp[l][1];
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a, b;
  cin >> a >> b;
  ll ans = (b - a + 1) - (func(b) - func(a - 1));
  cout << ans << "\n";
  return 0;
}