TopCoderOpen 2018 Argentina Round Hard ProbabilisticAlice

勉強になったので一応。
http://community.topcoder.com/stat?c=problem_statement&pm=14990

問題

２次元のグリッドが与えられる。
プレイヤーは左上角から初めて、右または下の隣接マスを辿り右下角に移動する。
なお、右と下どちらも移動可能な際は、確率pで右を選択する。

一部のマスは、左上角に強制的にプレイヤーをワープさせるマスである。
この時、右下マスに到達するまでワープ回数の期待値を答えよ。

解法

良くある手段として、確率に対し連立方程式を立てそれを掃出し法などで解くことができる。
この問題も本来これで行けそうなものだが、long doubleでも精度が足りず失敗する。

そこで、右下に１発でたどり着くAを求めよう。
これはDPで簡単に行える。
解は1/A-1。

long double dp[21][21];

class ProbabilisticAlice {
	public:
	double computeExpectation(vector <string> grid, int pnum, int pden) {
		long double p=1.0*pnum/pden;
		int H=grid.size();
		int W=grid[0].size();
		int y,x;
		
		ZERO(dp);
		dp[0][0]=1;
		FOR(y,H) FOR(x,W) if(grid[y][x]!='T') {
			if(y==H-1 && x==W-1) break;
			if(y==H-1) {
				dp[y][x+1]+=dp[y][x];
			}
			else if(x==W-1) {
				dp[y+1][x]+=dp[y][x];
			}
			else {
				dp[y+1][x]+=dp[y][x]*p;
				dp[y][x+1]+=dp[y][x]*(1-p);
			}
		}
		
		long double A=dp[H-1][W-1], B=1-A;
		if(A==0) return -1;
		if(A==1) return 0;
		return 1/A-1;
		
	}
}

まとめ

グリッドサイズ的に掃き出し法解法がO((HW)^3)がちょうどいいと思っちゃうじゃない…。