mayoko’s diary

プロコンとかいろいろ。

SRM 472 div2 hard:RectangularIsland

TopCoder
問題

TopCoder Statistics - Problem Statement

解法

x 方向と y 方向の動きが独立であることを利用します(こういう系の AtCoder であったような気がするけどなんだっけ)。

x 方向に動く回数を sx, y 方向に動く回数を sy とすると, 回数がこのようになる確率は, comb[sx+sy][sx]/(2^(sx+sy)) になります。2^(sx+sy) だけ x 方向か y 方向に動くか選べ, そのうち x 方向に sx 回動くのは, comb[sx+sy][sx] だからです。

で, x 方向に sx 回動く時, 外におちない確率は, dpx[s][x] = (s 回目の step で, 座標が x にある確率) という dp を回せば簡単に求められます。

これらを用いるて, steps 回のうち x 方向に動く回数で場合分けして 落ちない確率を求めれば良いです。

あとは細かいことなのですが, 例えば comb[steps][sx] を求めるために配列 comb[5000][5000] とか取ると MLE で死にます。
配列の中で, 最終的に使いたいのは comb[steps][*] のみなので, comb[2][5000] を用意して上手くやりましょう。

また, dpx[s][x] についても, dpx[5000][1000] と取ると MLE します。これも, 最後の計算で必要なのは 1-dpx[s][0]-dpx[s][width+1] (要するに全体から外に出る確率を引いたもの) だけなので, dpx[2][1000] を用意して毎回の dp を更新しながら, memox[s] という配列に 1-dpx[s][0]-dpx[s][width+1] という値を保持しておくとかやっておく必要があります。

制約上仕方ないとはいえ, ちょっと MLE 対策が面倒でした。でもめっちゃ好きな問題です。

double dx[2][1010];
double dy[2][1010];
double memox[5055], memoy[5055];
double nCr[2][5015];

class RectangularIsland {
public:
    double theProbablity(int width, int height, int x, int y, int steps) {
        for (int i = 0; i < 2; i++) for (int j = 0; j < 1010; j++) nCr[i][j] = 0;
        nCr[0][0] = 1;
        for (int i = 1; i <= steps; i++) {
            int cur = i%2, prev = cur^1;
            nCr[cur][0] = nCr[prev][0]/2;
            for (int j = 1; j <= i; j++) {
                nCr[cur][j] = nCr[prev][j] + nCr[prev][j-1];
                nCr[cur][j] /= 2;
            }
        }
        for (int i = 0; i < 2; i++) {
            assert(i < 2);
            for (int j = 0; j < width+10; j++) dx[i][j] = 0;
            for (int j = 0; j < height+10; j++) dy[i][j] = 0;
        }
        memox[0] = memoy[0] = 1;
        dx[0][x+1] = 1;
        dy[0][y+1] = 1;
        for (int s = 0; s < steps; s++) {
            int cur = s%2, tar = cur^1;
            for (int x = 1; x <= width; x++) dx[tar][x] = 0;
            dx[tar][0] = dx[cur][0];
            dx[tar][width+1] = dx[cur][width+1];
            for (int x = 1; x <= width; x++) {
                dx[tar][x-1] += dx[cur][x]/2;
                dx[tar][x+1] += dx[cur][x]/2;
            }
            memox[s+1] = 1-dx[tar][0]-dx[tar][width+1];
            for (int y = 1; y <= height; y++) dy[tar][y] = 0;
            dy[tar][0] = dy[cur][0];
            dy[tar][height+1] = dy[cur][height+1];
            for (int y = 1; y <= height; y++) {
                dy[tar][y-1] += dy[cur][y]/2;
                dy[tar][y+1] += dy[cur][y]/2;
            }
            memoy[s+1] = 1-dy[tar][0]-dy[tar][height+1];
        }
        double ans = 0;
        for (int sx = 0; sx <= steps; sx++) {
            int sy = steps-sx;
            ans += nCr[steps%2][sx] * memox[sx] * memoy[sy];
        }
        return ans;
    }
};