yukicoder No.309 シャイな人たち (1)

問題

No.309 シャイな人たち (1) - yukicoder

解法

この問題に考え方が非常に似ています。mayokoex.hatenablog.com

各行について「手をあげる人の集合」を考えると, これは別の場合と独立に考えることができるので happy ということです。
具体的には, dp[r][s] = (r 行目の人のうち, 状態 s で表される人のみが手をあげる確率)という dp を考えます。

すると, dp[r][s] を決めるためには, r 行目の人のうち倉敷市を知ってる人の集合, および r-1 行目の人のうち手を上げた人の集合を考えて, これらの情報から r 行目で手を上げる人を決定します。
これを正直に書くと O(RC4^C) で辛いんですが, C++ でゴリ押しました。ただ, 単純に書くと TLE するので, いろいろ高速化しました。

まず, 知ってる人の集合がそうなる確率を前計算, 「隣の人の何人が手をあげれば自分も手をあげるか」の mask を与えた時, 手を上げる人の集合を前計算します。
また, dp[r][s] を求める際, r 行目で倉敷市を知ってる人の集合を先に列挙すると, 知らない人は絶対に手を挙げないことがわかるので, その人は無視するようにして高速化出来ます。

typedef double Real;

const int MAX = 11;
int P[MAX][MAX], S[MAX][MAX];

int memo[1<<(2*MAX)], rest[MAX];
Real pmemo[MAX][1<<MAX];
Real dp[MAX+1][1<<MAX];

int main() {
    int R, C;
    scanf("%d %d", &R, &C);
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) scanf("%d", &P[i][j]);
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) scanf("%d", &S[i][j]);
    for (int s = 0; s < 1<<(2*C); s++) {
        int tmp = s;
        queue<int> que;
        for (int i = 0; i < C; i++) {
            rest[i] = tmp%4;
            tmp /= 4;
            if (rest[i] == 0) que.push(i);
        }
        while (!que.empty()) {
            int now = que.front(); que.pop();
            if (now-1 >= 0) {
                rest[now-1]--;
                if (rest[now-1] == 0) que.push(now-1);
            }
            if (now+1 < C) {
                rest[now+1]--;
                if (rest[now+1] == 0) que.push(now+1);
            }
        }
        int& result = memo[s];
        for (int i = 0; i < C; i++) result |= (rest[i]<=0)<<i;
    }
    for (int r = 0; r < R; r++) for (int s = 0; s < (1<<C); s++) {
        double& prob = pmemo[r][s];
        prob = 1;
        for (int c = 0; c < C; c++) {
            if ((s>>c)&1) prob *= P[r][c]/100.;
            else prob *= (100-P[r][c])/100.;
        }
    }
    dp[0][0] = 1;

    for (int r = 0; r < R; r++) {
        for (int s1 = 0; s1 < (1<<C); s1++) {
            vector<int> check;
            int origin = 0;
            for (int i = 0; i < C; i++) {
                if ((s1>>i)&1) check.push_back(i);
                else origin |= 3<<(2*i);
            }
            for (int s0 = 0; s0 < (1<<C); s0++) {
                if (r == 0 && s0 > 0) break;
                Real prob = dp[r][s0]*pmemo[r][s1];
                if (prob == 0) continue;
                int mask = origin;
                for (int el : check) {
                    int score = min(3, S[r][el]-((s0>>el)&1));
                    score = max(0, score);
                    mask |= score<<(2*el);
                }
                dp[r+1][memo[mask]] += prob;
            }
        }
    }
    Real ans = 0;
    for (int i = 1; i <= R; i++) for (int s = 1; s < (1<<C); s++) {
        ans += dp[i][s] * __builtin_popcount(s);
    }
    printf("%.10lf\n", ans);
    return 0;
}