UnKoder #04 : Snake and Mongoose

GWコンテストのおかげでタイトルを読み間違えそうになりました。
https://www.hackerrank.com/contests/unkoder-04/challenges/snake-and-mongoose

問題

無限に続く１次元の直線の道に、ヘビとマングースが並んでいる。
号令をかけると、各動物は半々の確率で左か右に同じ速さで移動する。

移動中、異なる動物が遭遇すると互いに喧嘩して消滅する。
十分な時間が経った後、残っている動物数の期待値を求めよ。

解法

左から順に、dp[動物の位置][右向きの残ったヘビの数][右向きの残ったマングースの数]=その状態に至る確率、としてDPすればよい。

• 動物が1/2の確率で左に行こうとする場合、右向きの天敵が1体以上いるなら相殺して1匹減らす。
  • 天敵がいないなら、左に行った動物は最終的に残るので、その分答えに加算する。
• 右に行こうとする場合は、右向きの動物の数を加算してDPを続ける。
  • 全ての動物を処理したあと、dp[動物の位置][右向きの残ったヘビの数][右向きの残ったマングースの数]が正なら、その残った右向きの動物を答えに加味する。

int N;
string S;
double ret;
double dp[52][52][52];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	
	dp[0][0][0]=1;
	FOR(i,N) {
		FOR(x,N) FOR(y,N) {
			double cur=dp[i][x][y]*0.5;
			if(S[i]=='S') {
				// left
				if(y>0) dp[i+1][x][y-1] +=cur;
				else dp[i+1][x][y]+=cur, ret +=cur;
				
				// right
				dp[i+1][x+1][y] += cur;
			}
			else {
				// left
				if(x>0) dp[i+1][x-1][y] +=cur;
				else dp[i+1][x][y]+=cur, ret +=cur;
				
				// right
				dp[i+1][x][y+1] += cur;
			}
		}
	}
	FOR(x,N+1) FOR(y,N+1) ret += (x+y)*dp[N][x][y];
	
	_P("%.12lf\n",ret);
}

まとめ

最近は動物愛護条例の関係で、沖縄のハブ博物館ではハブ対マングースはやらないそうです。