AtCoder Beginner Contest #007 D : 禁止された数字

問題文

http://abc007.contest.atcoder.jp/tasks/abc007_4

問題概要

　整数 A, B が与えられる。区間 [ A, B ] 内の値であって、10 進数表記したときに 4 または 9 を含む値（禁止された値）の個数を求めよ。

解法

　値の範囲がかなり大きく、区間内の値を全て列挙することはできないので、より効率的な方法を考える必要があります。
　まず、[ A, B ] 内に含まれる禁止された値の数は、[ 0, B ] のそれから [ 0, A ) のそれを引いた値と一致します。従って、B の最大値未満の任意の整数を N として、[ 0, N ] の場合について解く問題に帰着されました。
　

[ 0, N ] の場合について解く

　上位の桁から順に数字を決めていくと考えると、決めた桁数と禁止されているか否かが一致する状態は同一視できそうです。更に、ある桁に入れる数字 d を決めるとき、N を超えないためには次のような場合分けが必要になります。

• より上位の桁で、一度以上 N 未満となる値を使った -> 何を入れても N を超えない
• それ以外 -> N の対応する桁の数字以下の数字しか入れられない

従って、先程の考えた状態のパラメータにこれに関する情報を加え、次のような DP を考えることができます。

• dp[ i 桁決定した ][ j := 禁止されている値かどうかのフラグ ][ k := N 未満が確定したかどうかのフラグ ] := 値の個数

状態の初期値は 0 で、dp[ 0 ][ 0 ][ 0 ] のみ 1 です。dp[ i ][ j ][ k ] からの状態遷移は、次に入れる数字 d を可能な範囲で全て試して、

• dp[ i + 1 ][ j || d == 4 || d == 9 ][ k || d < D ] を更新（ただし D は N の対応する桁の数字）

となります。
表を埋め終わったあと、N の桁数を L として、dp[ L ][ 1 ][ k ] の総和が答えです。

コード

using LL = long long;
template < typename T = int > using VT = vector<T>;
template < typename T = int > using VVT = VT< VT<T> >;

template < typename T > inline string toString( const T &a ){ ostringstream oss; oss << a; return oss.str(); };

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

LL solve( const LL N )
{
	const string S = toString( N );
	const int L = S.size();

	VT< VVT<LL> > dp( L + 1, VVT<LL>( 2, VT<LL>( 2 ) ) );
	dp[0][0][0] = 1;

	REP( i, 0, L )
	{
		const int D = S[i] - '0';

		REP( j, 0, 2 )
		{
			REP( k, 0, 2 )
			{
				REP( d, 0, k ? 10 : D + 1 )
				{
					dp[ i + 1 ][ j || d == 4 || d == 9 ][ k || d < D ] += dp[i][j][k];
				}
			}
		}
	}

	return accumulate( ALL( dp.back().back() ), 0LL );
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	LL a, b;
	cin >> a >> b;

	cout << solve( b ) - solve( a - 1 ) << endl;

	return 0;
}