Codeforces #597 Div2 E. Hyakugoku and Ladders

Div2とはいえ簡単目だったっぽい回。
http://codeforces.com/contest/1245/problem/E

問題

100マスの双六がある。一部のマスでは、それぞれ定められたマス数だけ追加で前に進める。
この追加の移動は、使用しても使用しなくてもよく、その都度任意に選択できる。
最後ゴールに近づいたとき、さいころの目がゴールを超えてしまいそうな場合、そのマスから動かない。

最適手を取るときのさいころを振る回数の期待値を求めよ。

解法

前方にしか進まない双六なので、ゴールに近い順にゴールまでのさいころの回数の期待値を埋めていけばよい。
もし現在地が前方移動を行うマスの場合、前方移動を行った場合と行わない場合の期待値で少ない方を取ればよい。

int A[10][10];
int id[10][10];
double dp[100],best[100];
int to[100];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int N=10;
	MINUS(to);
	FOR(y,N) {
		FOR(x,N) {
			if(y%2==0) {
				id[y][x]=y*10+x;
			}
			else {
				id[y][x]=y*10+9-x;
			}
		}
		FOR(x,N) {
			cin>>r;
			if(r>0) to[id[y][x]]=id[y-r][x];
		}
	}
	
	for(i=1;i<100;i++) {
		if(i<6) {
			dp[i]=6.0;
			FOR(j,i) dp[i]+=dp[j];
			dp[i]/=i;
			best[i]=dp[i];
		}
		else {
			dp[i]=6.0;
			FOR(j,6) dp[i]+=best[i-1-j];
			dp[i]/=6;
			best[i]=dp[i];
			if(to[i]>=0) {
				best[i]=min(best[i],dp[to[i]]);
			}
		}
	}
	_P("%.12lf\n",dp[99]);
}

まとめ

これDiv2 Eにしては簡単すぎないか。