kmjp's blog

競技プログラミング参加記です

Codeforces #237 Div2 D. Minesweeper 1D

Codeforces

なかなか面白いがめんどくさい問題。
http://codeforces.com/contest/404/problem/D

問題

1次元に並んだセルにおけるマインスイーパを考える。
各マスは、爆弾が置いてあるか、隣接マスの爆弾の数（０～２）が書かれている。
通常のマインスイーパと異なり、爆弾のないマスは必ず数字が書かれている。

初期状態としていくつかのマスの中身が与えられる。
他のマスを矛盾のないように埋めたとき、矛盾が生じないマス構成の組み合わせ数を答えよ。

解法

左2マス分の状態を持っておき、左から順にDPすればよい。

  • 見ているマスが0の場合
    • 左のマスが爆弾または２であることはありえない。
    • 左が０で2つ左が数字、または左が１で2つ左が爆弾ならOKなので、その時の組み合わせを加算していく。
  • 見ているマスが1の場合
    • 左のマスが２であることはありえない。
    • 左が爆弾で2つ左が１か２か爆弾、または左が０で2つ左が０か１、または左が１で２つ左が爆弾ならOKなので、その時の組み合わせを加算していく。
  • 見ているマスが2の場合
    • 左のマスは爆弾でなければならない。
    • 2つ左が１か２か爆弾ならOKなので、その時の組み合わせを加算していく。
  • 見ているマスが爆弾の場合
    • 左のマスは０であることはありえない。爆弾でなければならない。
    • 左が１なら2つ左は０か１、左が２なら2つ左は爆弾、左が爆弾なら2つ左は１か２か爆弾ならOKなので、その時の組み合わせを加算していく。

初期状態として左に０がある場合と１にある場合を仮定することで、一番左セルが数字でも爆弾でも問題なくDP出来る。

int L;
string S;

ll mo=1000000007;
ll dp[1000002][4][4];

void solve() {
	int f,i,j,k,l,x,y;
	cin>>S;
	L=S.size();
	
	dp[0][0][0]=1;
	dp[0][0][1]=1;
	FOR(i,L) {
		if(S[i]=='0' || S[i]=='?') {
			dp[i+1][1][0]=(dp[i+1][1][0]+dp[i][3][1])%mo;
			dp[i+1][0][0]=(dp[i+1][0][0]+dp[i][0][0])%mo;
			dp[i+1][0][0]=(dp[i+1][0][0]+dp[i][1][0])%mo;
			dp[i+1][0][0]=(dp[i+1][0][0]+dp[i][2][0])%mo;
		}
		if(S[i]=='1' || S[i]=='?') {
			dp[i+1][3][1]=(dp[i+1][3][1]+dp[i][3][3])%mo;
			dp[i+1][3][1]=(dp[i+1][3][1]+dp[i][1][3])%mo;
			dp[i+1][3][1]=(dp[i+1][3][1]+dp[i][2][3])%mo;
			dp[i+1][0][1]=(dp[i+1][0][1]+dp[i][0][0])%mo;
			dp[i+1][0][1]=(dp[i+1][0][1]+dp[i][1][0])%mo;
			dp[i+1][1][1]=(dp[i+1][1][1]+dp[i][3][1])%mo;
		}
		if(S[i]=='2' || S[i]=='?') {
			dp[i+1][3][2]=(dp[i+1][3][2]+dp[i][3][3])%mo;
			dp[i+1][3][2]=(dp[i+1][3][2]+dp[i][1][3])%mo;
			dp[i+1][3][2]=(dp[i+1][3][2]+dp[i][2][3])%mo;
		}
		if(S[i]=='*' || S[i]=='?') {
			dp[i+1][1][3]=(dp[i+1][1][3]+dp[i][0][1])%mo;
			dp[i+1][1][3]=(dp[i+1][1][3]+dp[i][1][1])%mo;
			dp[i+1][2][3]=(dp[i+1][2][3]+dp[i][3][2])%mo;
			dp[i+1][3][3]=(dp[i+1][3][3]+dp[i][1][3])%mo;
			dp[i+1][3][3]=(dp[i+1][3][3]+dp[i][2][3])%mo;
			dp[i+1][3][3]=(dp[i+1][3][3]+dp[i][3][3])%mo;
		}
	}
	
	ll ret=dp[L][0][0]+dp[L][1][0]+dp[L][3][1]+dp[L][1][3]+dp[L][2][3]+dp[L][3][3];
	cout << ret%mo << endl;
}

まとめ

ちょっとややこしいDP。
2つ前まで状態を持つDPは以前Codeforcesで出てきたおかげで書けた。