[AtCoder] ABC 007 D – 禁止された数字
問題
方針
桁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; }
ディスカッション
コメント一覧
まだ、コメントがありません