はまやんはまやんはまやん

hamayanhamayan's blog

Lamps [HHKB プログラミングコンテスト 2020 E]

競技プログラミング

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_e

前提知識

解説

https://atcoder.jp/contests/hhkb2020/submissions/17319314

初めて見る人には何から手を付けるべきか分からない問題であるように思う。
2K通りをすべて考えるのは不可能問題。
こういう時はどういうテクを使えばいいだろうか。

主客転倒

「2K通りすべてについて、照らされているマスの総和を計算して、その総和を答える」という問題であるが、
主客転倒テクを使う。
「K通りのマスについて、そのマスが照らされる組み合わせを計算して、その総和を答える」と変換する。
主客転倒テクをやったことがない人はなんのことだかという感じであると思うが、知っていればそれほど難しくない。
分からない場合は、以下を読んで学ぼう。
あの〜、お詫びと言っては何ですけどちょっと数え上げでよく見るらしい「主客転倒」の解説今から書くんで… - physics0523's 精進ログ

これで全通りする部分が現実的な個数となった。

あるマスが照らされる組み合わせ

とあるマスが照らされる組み合わせを計算するにはどうすればいいだろう。
そのマスが照らされるには、そのマスから上下左右にある散らかっていないマスのいずれかに照明が置かれていればいい。
いずれかというのは少し計算が面倒なので、補事象を使おう。
全体から「そのマスから上下左右にある散らかっていないマスのいずれにも照明が置かれていない」を引いて計算することにする。
全体は2K通り。
「そのマスから上下左右にある散らかっていないマスのいずれにも照明が置かれていない」組合せは、
上下左右にある散らかっていないマスの個数をcnt個とすると、2K-cnt通りである。
これはcnt個の部分は照明が置かれていなくて、他は何でもいいからである。
よって、あとは「上下左右にある散らかっていないマスの個数」が分かれば答えが導ける。

上下左右にある散らかっていないマスの個数

これは二次元累積和と二分探索を使って計算できる。
二次元累積和を使ってある区間に含まれる散らかっていないマスの個数を高速に持ってこれるようにしておこう。
あとは、上下左右について二分探索を使って、選択している区間=散らかっていないマスの個数となるように伸ばせる区間の最大長を特定すれば、
上下左右にあるマスの個数が分かり、上下左右にある散らかっていないマスの個数を計算することができる。
この部分はより筋の良い方法がたぶんある。

int H, W;
string S[2020];
mint pr[4101101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) cin >> S[y];

    pr[0] = 1;
    rep(i, 1, 4101101) pr[i] = pr[i - 1] * 2;

    Ruisekiwa2D emp(W, H);
    int K = 0;
    rep(y, 0, H) rep(x, 0, W) if (S[y][x] == '.') emp.add(x, y, 1), K++;
    emp.build();

    mint ans = 0;
    rep(y, 0, H) rep(x, 0, W) if(S[y][x] == '.') {
        int cnt = 1;
        rep(d, 0, 4) {
            int ok = 1, ng = 2020;
            while (ok + 1 != ng) {
                int md = (ok + ng) / 2;
                if (emp.getTo(x, y, md, d) == md) ok = md;
                else ng = md;
            }
            cnt += ok - 1;
        }
        ans += pr[K] - pr[K - cnt];
    }
    cout << ans << endl;
}