SRM 472 Div2 Hard RectangularIsland

問題

http://apps.topcoder.com/stat?c=problem_statement&pm=10945&rd=14154

width * height のグリッド上の(x,y)にあなたが立っている。一回の移動で上下左右のセルに同じ確率で動ける。steps回移動した後にグリッドから落ちていない確率を求めよ。
制約はwidth, height <= 1000、steps <= 5000

やりかた

practice roomのsdyaさんのコードを参考にしました。

制約が厳しいのでDPもできない。そこで考え方を変える。
steps回移動するうちで、i回の上下移動があるとすると、左右移動の回数は(steps - i)回になる。ここで上下移動のみについて考えると、次の上下移動でj行目にいる確率next[j]はnext[j] = (cur[j - 1] + cur[j + 1]) / 2で計算できる（ソース中ではtmpv[j],v[j]となっている）。jを0〜widthまで動かして、それぞれの行にいる確率を求める。
この処理をsteps回行なって毎回、その回(iとする)で0 ~ widthの間にいる確率の和を求めておく（alivev[i]）。これはi回の上下移動でプレイヤーがグリッドの外に出ないで生き残っている確率になる。
左右運動についても同様に計算する。
これが求まれば、steps回の移動で上下移動がi回の時の最終的に生き残る確率は

あとはこれをiを0~stepsで動かして和を取ればいい。

以下ソース。

double v[1002], h[1002];
double tmpv[1002], tmph[1002];
double alivev[5002], aliveh[5002];

class RectangularIsland {
public:
  double theProbablity(int width, int height, int x, int y, int steps) {
    memset(v, 0, sizeof(v)); 
    memset(h, 0, sizeof(h));
    memset(tmpv, 0, sizeof(tmpv)); 
    memset(tmph, 0, sizeof(tmph));
    memset(alivev, 0, sizeof(alivev)); 
    memset(aliveh, 0, sizeof(aliveh));

    v[y + 1] = 1.0;
    h[x + 1] = 1.0;
    alivev[0] = 1.0;
    aliveh[0] = 1.0;
    for(int i = 1; i <= steps; i++){
      for(int j = 1; j <= height; j++){
	tmpv[j] = (v[j - 1] + v[j + 1]) / 2.0;
	alivev[i] += tmpv[j];
      }
      for(int j = 1; j <= height; j++) 
	v[j] = tmpv[j];
      
      for(int j = 1; j <= width; j++){
	tmph[j] = (h[j - 1] + h[j + 1]) / 2.0;
	aliveh[i] += tmph[j];
      }
      for(int j = 1; j <= width; j++)
	h[j] = tmph[j];
    }

    double ret = 0.0;
    for(int i = 0; i <= steps; i++){
      double t = pow(2.0, -steps);
      for(int j = 1; j <= i; j++)
	t *= (double)(steps - j + 1) / j;
      
      ret += t * alivev[i] * aliveh[steps - i];
    }
    return ret;
  }
};

sdyaさんのコードは非常に簡潔でいつも参考になる。v[j], h[j]の計算で境界の計算を避けてるところとかうまい。

とても良い問題だと思う。勉強になった。こういうのができるようになりたい。