Zenn
🕌

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

2023/11/19に公開
#
競技プログラミング
AtCoder
#
競プロ
#
確率
idea

問題

問題

解説（ネタバレ注意！）

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

全体の 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;
}

ライブラリ

Discussion