Codeforces #179, Division 2, B : Yaroslav and Two Strings

問題文

http://codeforces.com/contest/296/problem/B

概要

二つの数字からなる文字列 s, t について、比較不能であるとは次の条件を満たす i, j が存在することを言う。
かつ

数字と '?'　からなる二つの文字列が与えられる。
二つの文字列が比較不能となるように '?' に数字を入れる入れ方の総数を求めよ。

解法

条件を分解して、条件1 := 、条件2 := と置きます。
dp[ 位置 ][ 条件 1 を既に満たしたか ][ 条件 2 を既に満たしたか ] := この状態へ至る置き方の総数
として動的計画法（ digit DP 、 桁 DP ）をすると求まります。

コード

typedef long long LL;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

const int MOD = 1000000007;

typedef vector< LL > VLL;
typedef vector< VLL > VVLL;

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

	int n;
	cin >> n;

	string s, t;
	cin >> s >> t;

	vector< VVLL > dp( n + 1, VVLL( 2, VLL( 2, 0 ) ) );
	dp[0][0][0] = 1;

	REP( i, 0, n )
	{
		REP( j, 0, 2 )
		{
			REP( k, 0, 2 )
			{
				dp[i][j][k] %= MOD;

				if ( s[i] == '?' && t[i] == '?' )
				{
					REP( x, 0, 10 )
					{
						REP( y, 0, 10 )
						{
							dp[ i + 1 ][ j | ( x < y ) ][ k | ( x > y ) ] += dp[i][j][k];
						}
					}
				}
				else if ( s[i] == '?' )
				{
					const int A = t[i] - '0';
					REP( x, 0, 10 )
					{
						dp[ i + 1 ][ j | ( x < A ) ][ k | ( x > A ) ] += dp[i][j][k];
					}
				}
				else if ( t[i] == '?' )
				{
					const int A = s[i] - '0';
					REP( y, 0, 10 )
					{
						dp[ i + 1 ][ j | ( A < y ) ][ k | ( A > y ) ] += dp[i][j][k];
					}
				}
				else
				{
					dp[ i + 1 ][ j | ( s[i] < t[i] ) ][ k | ( s[i] > t[i] ) ] += dp[i][j][k];
				}
			}
		}
	}

	cout << dp.back()[1][1] % MOD << endl;

	return 0;
}