kmjp's blog

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

CSAcademy Round #46 : F. Combinatorix

その他コンテスト

あと一歩で本番通せず。
https://csacademy.com/contest/round-46/task/combinatorix/

問題

N*Mのグリッドがある。各マスは

  • 埋まっていて移動不可
  • 空いていて移動可
  • 両者どちらかわからない(不定マス)

プレイヤーは初期位置として1列目のR1行目におり、M列目のR2行目に移動したい。
移動は以下の判定を順に行い、最初に条件を満たした項目の通りに行う。
目的地に到達できる不定マスの組み合わせは何通りか。

  • すでに目的地に到達したならそれ以上移動しない。
  • 上のマスが、空きマスかつ未経由のマスなら上に移動する。
  • 右について同上
  • 下について同上
  • 上記いずれでもない場合、それ以上移動しない。

解法

不定マスをa個とすると、全体で2^a通りの組み合わせがある。
移動先の候補が不定マスだった場合、半分はそこが空マス、残り半分は埋まったマスと考えて組み合わせを半分ずつ振り分ければよい。

移動先の判定はマスの状態に加え、自身が経由したかどうかも考慮される。
よって直前２回の移動経路を覚えつつDPしていけばよい。直前の移動経路により、下記経路はたとえ空きマスでも取れない。

  • 直前上移動した場合　：　下移動はしない。
  • 直前下移動した場合　：　上移動はしない。
  • 直前２回下・右と移動した場合：上移動はしない。
  • それ以外（上・右および右・右）の場合：　移動経路による制限はない。
int H,W,R1,R2;
string S[1010];
ll mo=1000000007;
ll dp[1010][1010][5]; //U,D,UR,DR,RR
int D;
ll r2=(mo+1)/2;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>R1>>R2;
	R1--,R2--;
	FOR(y,H) cin>>S[y];
	
	if(S[R1][0]=='1') return _P("0\n");
	if(S[R2][W-1]=='1') return _P("0\n");
	S[R1][0]='0';
	S[R2][W-1]='0';
	FOR(y,H) S[y]="1"+S[y];
	W+=1;
	S[R1][0]='0';
	
	FOR(y,H) FOR(x,W) if(S[y][x]=='?') D++;
	
	dp[R1][0][4]=1;
	FOR(x,W) {
		// go down
		FOR(y,H-1) if(S[y+1][x]!='1') {
			ll p=1;
			if(x<W-1 && S[y][x+1]=='0') continue;
			if(x<W-1 && S[y][x+1]=='?') p=p*r2%mo;
			if(S[y+1][x]=='?') p=p*r2%mo;
			(dp[y+1][x][1]+=p*(dp[y][x][1]+dp[y][x][3]))%=mo;
			if(y&&S[y-1][x]=='0') continue;
			if(y&&S[y-1][x]=='?') p=p*r2%mo;
			(dp[y+1][x][1]+=p*(dp[y][x][2]+dp[y][x][4]))%=mo;
		}
		// go up
		for(y=H-1;y>=1;y--) if(S[y-1][x]!='1') {
			ll p=1;
			if(S[y-1][x]=='?') p=r2;
			(dp[y-1][x][0]+=p*(dp[y][x][0]+dp[y][x][2]+dp[y][x][4]))%=mo;
		}
		// go right
		FOR(y,H) if(x<W-1 && S[y][x+1]!='1') {
			ll p=1;
			if(S[y][x+1]=='?') p=p*r2%mo;
			
			(dp[y][x+1][3]+=p*dp[y][x][1])%=mo;
			(dp[y][x+1][4]+=p*dp[y][x][3])%=mo;
			
			if(y&&S[y-1][x]=='0') continue;
			if(y&&S[y-1][x]=='?') p=p*r2%mo;
			(dp[y][x+1][2]+=p*dp[y][x][0])%=mo;
			(dp[y][x+1][4]+=p*(dp[y][x][2]+dp[y][x][4]))%=mo;
		}
	}
	
	ll a=(dp[R2][W-1][0]+dp[R2][W-1][1]+dp[R2][W-1][2]+dp[R2][W-1][3]+dp[R2][W-1][4]);
	while(D--) a=a*2%mo;
	
	cout<<a%mo<<endl;
}

まとめ

２手覚えることに気づくまで時間がかかった。