Codeforces #596 Div1 C. Rock Is Push

ありそうでなかった問題？
http://codeforces.com/contest/1246/problem/C

問題

H*Wのグリッドがあり、いくつかのマスには岩が置いてある。
このグリッドで左上マスから右下マスに、右か下のマスへの移動を繰り返して到達したい。
その際、移動先に岩がある場合、進行方向にその岩を押すことができる。
押した先にも岩がある場合、複数まとめて押すこともできるが、先頭の岩がグリッド外に出るような押し方はできない。
到達方法は何通りか。

解法

各マスに到達した際、直前に左から侵入してきたか上から侵入してきたかに応じて2通り状態を持っておき、次は別の方向に移動しよう。
その場合、直前の侵入で押してきた岩を考慮する必要がなくなる。
また、移動時は(岩をグリッド外に押す必要がない範囲で)一気に同じ方向に複数マス移動できることになる。
これは累積和を使えば処理できる。

int H,W;
string S[2020];
int R[2020][2020];
int D[2020][2020];
const ll mo=1000000007;
ll dp[2020][2020][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		for(x=W-1;x>=0;x--) {
			R[y][x]=R[y][x+1];
			if(S[y][x]=='R') R[y][x]++;
		}
	}
	FOR(x,W) {
		for(y=H-1;y>=0;y--) {
			D[y][x]=D[y+1][x];
			if(S[y][x]=='R') D[y][x]++;
		}
	}
	if(H==1 && W==1) return _P("1\n");
	dp[0][0][0]=dp[0][0][1]=1;
	dp[0][1][0]=mo-1;
	dp[1][0][1]=mo-1;
	FOR(y,H) FOR(x,W) {
		if(x) {
			dp[y][x][0]+=dp[y][x-1][0];
		}
		if(y) {
			dp[y][x][1]+=dp[y-1][x][1];
		}
		dp[y][x][0]%=mo;
		dp[y][x][1]%=mo;
		// down
		int tar=H-1-D[y+1][x];
		dp[y+1][x][1]+=dp[y][x][0];
		dp[tar+1][x][1]+=mo-dp[y][x][0];
		tar=W-1-R[y][x+1];
		dp[y][x+1][0]+=dp[y][x][1];
		dp[y][tar+1][0]+=mo-dp[y][x][1];
	}
	cout<<(dp[H-1][W-1][0]+dp[H-1][W-1][1])%mo<<endl;
	
}

まとめ

本番もこれは割とすんなり解けてた。