キーエンス プログラミング コンテスト 2021 : C - Robot on Grid

良くも悪くもなかった回。
https://atcoder.jp/contests/keyence2021/tasks/keyence2021_c

問題

H*Wのグリッドがある。
K箇所のマスは、R,D,Xのいずれかが書かれており、その内容が指定される。

駒を左上マスに置き、右または下の隣接マスへの移動を繰り返し右下マスに移動することを考える。
その際、マスにDと書かれている場合は右に移動できず、Rと書かれている場合は下に移動できないとする。
内容未指定の(HW-K)マスにR,D,Xのどれを書くかは、計3^(HW-K)通り考えられる。
それぞれのケースにおいて、左上から右下マスに移動する経路の総和を求めよ。

解法

内容未指定のマスが1/3の確率でR,D,Xを取るとして、各経路をたどれる期待値の総和を求めよう。
内容未指定のマスの場合、右または下に移動できる確率を2/3とみなし、DPで求めて行けばよい。

int H,W,K;
char S[5050][5050];
ll dp[5050][5050];
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	FOR(i,K) {
		cin>>y>>x>>s;
		S[y-1][x-1]=s[0];
	}
	dp[0][0]=1;
	ll re=1;
	ll a=2*modpow(3);
	FOR(y,H) FOR(x,W) {
		if(S[y][x]==0) {
			re=re*3%mo;
			(dp[y+1][x]+=dp[y][x]*a)%=mo;
			(dp[y][x+1]+=dp[y][x]*a)%=mo;
		}
		else {
			if(S[y][x]=='D'||S[y][x]=='X') (dp[y+1][x]+=dp[y][x])%=mo;
			if(S[y][x]=='R'||S[y][x]=='X') (dp[y][x+1]+=dp[y][x])%=mo;
		}
	}
	cout<<dp[H-1][W-1]*re%mo<<endl;
	
}

まとめ

ABCの500ptよりはだいぶ難しい気がする。