HHKB2020-E Lamps (確率ベースで考える方法)

問題

問題

解説（ネタバレ注意！）

公式解説と少し違ったアプローチをしたので、記事にしておきます。

全体の $2^K$ 通りにおいて、マス $(i, j)$ が照らされている確率 $P_{i, j}$ を求め、それに $K$ を掛けたものの合計が答えになります。

• $(i, j)$ と同じマス
• $(i, j)$ と同じ行のマス
• $(i, j)$ と同じ列のマス

に照明が置かれたとき、そのマスは照らされます。

各マスが照らされるのは、全体の $\frac{1}{2}$ です。

ここで、逆に照らされない時の確率を求めます、その値を $1$ から引いたものが $P_{i, j}$ です。

つまり、上記 $3$ つのパターンに該当するマスの和の数を $L$ とすると、それは

$$1 - P_{i, j} = (1 - \frac{1}{2})^K$$

となります。

実装例

$L$ の数を求めるのを、 union-findでサボりました。

void solve(){
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h)cin >> s[i];
    
    union_find uf_row(h * w), uf_col(h * w);

    rep(i, h)rep(j, w - 1){
        if(s[i][j] == '.' && s[i][j + 1] == '.')uf_col.unite(i * w + j, i * w + j + 1);
    }
    rep(i, h - 1)rep(j, w){
        if(s[i][j] == '.' && s[i + 1][j] == '.')uf_row.unite(i * w + j, (i + 1) * w + j);
    }

    int k = 0;
    rep(i, h)rep(j, w)if(s[i][j] == '.')k++;
    mint pow = 1;
    rep(_, k)pow *= 2;

    vector<mint> p2(k + 1);
    p2[0] = 1;
    rep(i, k)p2[i + 1] = p2[i] / mint(2);

    mint ans = 0;
    rep(i, h)rep(j, w){
        if(s[i][j] == '#')continue;
        ans += (mint(1) - p2[uf_col.get_size(i * w + j) + uf_row.get_size(i * w + j) - 1]) * pow;
    }
    cout << ans << endl;
}

ライブラリ