Codeforces #237, D : Minesweeper 1D

問題文

http://codeforces.com/contest/404/problem/D

問題概要

　一次元でのマインスイーパーを考える。盤面は文字列で表され、各文字は "*012" のいずれかである。'*' は爆弾を表し、数字は隣接するセルに存在する爆弾の数の合計を表す。
　今、"*012" に '?' を加えた文字列が与えられる。全ての '?' を "*012" のいずれかに（独立に）変化させて得られる valid な盤面がいくつあるか、MOD で求めよ。

解法

　与えられた文字列の長さを L と表記します。
　左から一文字ずつ決めていくと考えます。普通にやると状態数が になってやばいので、選択肢が等しくなる状態を同一視する DP を考えます。このとき、可能な選択肢を識別できるように状態をとる必要がありますが、どの数字を置けるかを決めるためには直前のセルに爆弾を置いたかどうかの情報が必要となり、爆弾を置けるかどうかを決めるためには直前の数字に関係する情報が必要となります。少し簡略化しつつ状態をとると、次のような DP を考えることができます。

• dp[ i 箇所決定した ][ j := 直前に爆弾を置いたなら true ][ k := 爆弾設置の自由度を識別する値 ] := 総数

k の値は、

• 0 : 任意
• 1 : 爆弾を位置けない
• 2 : 爆弾を置かなければならない

を表すとします。
　状態遷移はどの文字を置くかの 4 通りです。共通する性質として、対応する位置の文字が選択肢を表す文字と等しいか、または '?' である必要があります。共通かつ自明なので以下では省略します。各選択肢について、次のように更新します。

• 爆弾を置く（ k != 1 のとき可能）：dp[ i + 1 ][ 1 ][ 0 ] を更新
• '0' を置く（ j = 0 && k != 2 のとき可能）：dp[ i + 1 ][ 0 ][ 1 ] を更新
• '1' を置く（ k != 2 のとき可能）：dp[ i + 1 ][ 0 ][ 2 - j ] を更新
• '2' を置く（ j = 1 && k != 2 のとき可能）：dp[ i + 1 ][ 0 ] [2 ] を更新

　計算が終わった後、k = 2 を除く j, k について dp[ L ][ j ][ k ] の総和が答えになります。k == 2 の場合を除くのは、k = 2 が表すのは次のセルに爆弾を置かないと valid にならない状態を示しているからです。

コード

typedef vector<int> VI;
typedef vector<VI> VVI;

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

const int MOD = 1000000007;

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

	const int L = str.size();

	vector<VVI> dp( L + 1, VVI( 2, VI( 3, 0 ) ) );
	dp[0][0][0] = 1;

	REP( i, 0, L )
	{
		REP( j, 0, 2 )
		{
			REP( k, 0, 3 )
			{
				if ( str[i] == '?' || str[i] == '*' ) 
				{
					if ( k != 1 )
					{
						( dp[ i + 1 ][1][0] += dp[i][j][k] ) %= MOD;
					}
				}
				if ( str[i] == '?' || str[i] == '0' )
				{
					if ( !j && k != 2 )
					{
						( dp[ i + 1 ][0][1] += dp[i][j][k] ) %= MOD;
					}
				}
				if ( str[i] == '?' || str[i] == '1' )
				{
					if ( k != 2 )
					{
						( dp[ i + 1 ][0][ 2 - j ] += dp[i][j][k] ) %= MOD;
					}
				}
				if ( str[i] == '?' || str[i] == '2' )
				{
					if ( j && k != 2 )
					{
						( dp[ i + 1 ][0][2] += dp[i][j][k] ) %= MOD;
					}
				}
			}
		}
	}

	int res = 0;
	REP( j, 0, 2 )
	{
		REP( k, 0, 2 )
		{
			( res += dp.back()[j][k] ) %= MOD;
		}
	}
	cout << res << endl;

	return 0;
}