UnKoder #04

UnKoder #04 に参加しました。結果は内緒です。
topcoder以外のコンテストはたいていサンプルが甘いのでちゃんと注意深く問題を把握しないとダメですね。これからは意識的に気をつけていきたいです(C問題を単純な期待値の線形性を使ってやろうとしてハマった)。

問題

Programming Problems and Competitions :: HackerRank

解法

一応ハマったので言っておくと,これは単純なアイデアで期待値の線形性を使っても解けません。具体的には,「i番目とj番目がペアで消滅する条件にその間でSMが消滅する場合」をちゃんと考える必要があります。僕は完全にそのことを忘れてなんでなんでと言っていました。アホですね。

じゃあどうやれば良いかというと,dpを使います。
p[n][s][m] = (0からnまでの動物を見ていった時,右側から蛇がs匹とマングースがm匹出てくる確率)
e[n][s][m] = (0からnまでの動物を見ていった時,左側から出てくる動物の期待値)
とします。すると,ソースコードのように漸化式が作れます。

以下ソースコード

const int MAXN = 55;

double p[MAXN][MAXN][MAXN];
double e[MAXN][MAXN][MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int N = s.size();
    for (int i = 0; i < MAXN; i++) for (int j = 0; j < MAXN; j++) for (int k = 0; k < MAXN; k++) {
        p[i][j][k] = 0;
        e[i][j][k] = 0;
    }
    p[0][0][0] = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= N; j++) {
            for (int k = 0; k <= N; k++) {
                if (p[i][j][k] == 0) continue;
                if (s[i] == 'S') {
                    // move left
                    if (k == 0) {
                        p[i+1][j][k] += p[i][j][k] / 2;
                        e[i+1][j][k] += e[i][j][k] / 2 + p[i][j][k]/2;
                    } else {
                        p[i+1][j][k-1] += p[i][j][k] / 2;
                        e[i+1][j][k-1] += e[i][j][k] / 2;
                    }
                    // move right
                    p[i+1][j+1][k] += p[i][j][k] / 2;
                    e[i+1][j+1][k] += e[i][j][k] / 2;
                } else {
                    // move left
                    if (j == 0) {
                        p[i+1][j][k] += p[i][j][k] / 2;
                        e[i+1][j][k] += e[i][j][k] / 2 + p[i][j][k]/2;
                    } else {
                        p[i+1][j-1][k] += p[i][j][k] / 2;
                        e[i+1][j-1][k] += e[i][j][k] / 2;
                    }
                    // move right
                    p[i+1][j][k+1] += p[i][j][k] / 2;
                    e[i+1][j][k+1] += e[i][j][k] / 2;
                }
            }
        }
    }
    double ans = 0;
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= N; j++) {
            ans += e[N][i][j] + (i+j) * p[N][i][j];
        }
    }
    printf("%.15lf\n", ans);
    return 0;
}