ありそうでなかった問題?
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; }
まとめ
本番もこれは割とすんなり解けてた。