Codeforces 24 D. Broken robot
問題
N行M列のグリッドがある。
このグリッドのi行j列にロボットがいて、
ロボットは1ターンに1度次の動きのうち、可能なものを等確率で一つ実行する。
- その場から動かない
- 一列下の列に動く(最下段についたら止まる)
- 左に動く(グリッドからはみでる場合は不可能)
- 右に動く(上に同じ)
ロボットが停止するまでにかかるターン数の期待値を小数点4桁まで求めよ。
制約条件
N,M≦1000
方針
ある一行の期待値が全て求まっていれば、その一行上の行の期待値は、
1000次の連立方程式を解くことで決定できる。
しかし、1000次の連立方程式を1000回解くのは計算時間が間に合わない。
そのため、期待値が収束するまで100回程度ループを回してやる。
これで必要な精度の答えが計算できる。
ソースコード
const int iter=100; int n,m,y,x; double e[1000][1000]; void run(){ cin>>n>>m>>y>>x; y--; x--; if(y==n-1){ cout<<0<<endl; return; } for(int i=n-2;i>=y;i--){ rep(_,iter)rep(j,m){ int cnt=2; double s=e[i+1][j]+e[i][j]; if(j>0)s+=e[i][j-1], cnt++; if(j<m-1)s+=e[i][j+1], cnt++; e[i][j]=1+s/cnt; } } printf("%.9f\n",e[y][x]); }