ABC007 D - 禁止された数字

概要

10進数表記で4, 9を含む数字が禁止されているとき、整数A, BについてA以上B以下の整数で禁止された数字はいくつあるか。

制約

1 ≦ A ≦ B ≦ 10^18

方針

桁DP。

解答①

ペケンペイさんのを参考に。
pekempey.hatenablog.com
制約はすべてループで考慮し、代入式は1つ。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
ll calc(ll N){
	string A = to_string(N);
 
	// 桁DP
	ll dp[55][2][2];
	// dp[i][j][k]
	// i桁目までが確定
	// j=0ならNと等しい可能性があり、j=1ならNより真に小さい
	// k=1ならすでに禁止されている
	memset(dp, 0, sizeof(dp));
	dp[0][0][0] = 1;
 
	for(int i = 0; i < A.size(); i++){
		for(int j = 0; j < 2; j++){
			for(int k = 0; k < 2; k++){
				int x = j == 0 ? A[i] - '0' : 9;
				for(int d = 0; d <= x; d++){
					dp[i+1][j || d < x][k || d == 4 || d == 9] += dp[i][j][k];
				}
			}
		}
	}
 
	return dp[A.size()][0][1] + dp[A.size()][1][1];
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll A, B;
	cin >> A >> B;
 
	cout << calc(B) - calc(A-1) << endl;
}

解答②

けんちょんさんのを参考に。
drken1215.hatenablog.com
Submission #1964860 - AtCoder Beginner Contest 007

禁止されていない数字の個数を求める。
0->0, 0->1, 1->1の推移を明示的にしている。

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
ll calc(ll N){
	string str = to_string(N);
 
	// 桁DP
	ll dp[55][2];
	// dp[i][j] : i桁目までが確定、j=0ならNと等しい可能性があり、j=1ならNより真に小さい
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
 
	for(int i = 0; i < str.size(); i++){
		int next = (int)(str[i] - '0');
 
		// 0 -> 0
		if(next != 4 && next != 9){
			// cout << "0->0: " << i << "," << dp[i][0] << "," << dp[i+1][0] << endl;
			dp[i+1][0] += dp[i][0];
		}
 
		// 0 -> 1, 1 -> 1
		for(int j = 0; j < 10; j++){
			if(j == 4 || j == 9) continue;
			if(j < next) {
				// cout << "0->1: " << i << "," << j << "," << dp[i][0] << "," << dp[i+1][1] << endl;
				dp[i+1][1] += dp[i][0];
			}
			// cout << "1->1: " << i << "," << j << "," << dp[i][1] << "," << dp[i+1][1] << endl;
			dp[i+1][1] += dp[i][1];
		}
	}
 
	ll res = N - (dp[str.size()][0] + dp[str.size()][1]);
	return res;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll A, B;
	cin >> A >> B;
 
	cout << calc(B) - calc(A-1) << endl;
}