E - Lamps HHKB2020 - hotarunx's diary

問題情報

問題名: E - Lamps
配点: 500点
コンテスト: HHKB プログラミングコンテスト 2020（ABC相当）
Difficulty: 1358

Dが青💙、Fが橙🧡なのでこれを解かないとパフォが絶望的になる。

キーワード

グリッド・累積和・余剰・数え上げ・繰り返し二乗法

考えたこと

解説と解き方が違ったわ。

照明の置き方は $2 ^ K$ あるため全探索するともちろんTLEです。照明の置き方ではなくてマスに着目すればいいのではないか？問題を 「散らかっていないK個のマスそれぞれについて、マスを照らす照明の置き方の個数を計算する」 と読み替える。

「照明が置かれたとき、マス $(i,j)$ を照らすマス」を①と呼ぶ。
「照明が置かれたとき、マス $(i,j)$ を照らさないマス」を②と呼ぶ。

（マス $(i,j)$ を照らす照明の置き方）＝（①へ照明を1個以上置く照明の置き方）X（②への照明の置き方）である。

①の数を $L _ {i,j}$ とする。（①へ照明を1個以上置く照明の置き方）＝（①への全置き方）-（照明を1つも置かない置き方）＝ $2 ^ {L _ {i,j}} - 1$ 。（②への照明の置き方）＝ $2 ^ {K - L _ {i,j}}$ 。

ゆえに（マス $(i,j)$ を照らす照明の置き方）＝ $(2 ^ {L _ {i,j}} - 1)2 ^ {K - L _ {i,j}}$

累乗は繰り返し二乗法で高速に計算しよう。 $L _ {i,j}$ を素早く求められれば、計算量が十分になる。

例えばこういうテストケースでマス $(2,2)$ を照らす照明の置き方を考える。

2 8
..####..
....##..

①は赤線で囲んだ5マス。マス $(2,2)$ を照らす照明の置き方は $(2 ^ 5 -1) 2 ^ {10 - 5}$ 。

では $L _ {i,j}$ を求めよう。先程のテストケースでは $L _ {i,j}$ は次のようになる。

33000033
55440033

$L _ {i,j}$ ＝（横方向の連続な散らかっていないマスの数）＋（縦方向の連続な散らかっていないマスの数）ー1である。

マス $(i,j)$ の横方向の連続な散らかっていないマスの数を $A(i,j)$ とする。先程のテストケースでは $A(i,j)$ は次のようになる。

22000022
44440022

$A(i,j)$ は次の手順で求められる。

から順に次の漸化式でを更新する。
1. マス(i,j)が散らかっていないならば $A(i,j)=A(i,j-1)+1$ 。
2. マス(i,j)が散らかっているならば $A(i,j)=0$ 。

から順に次の漸化式でを更新する。
1. マス(i,j)が散らかっていないならば $A(i,j)=max(A(i,j+1),A(i,j)$ 。
2. マス(i,j)が散らかっているならば $A(i,j)=0$ 。

$A(i,j)$ の計算量は $O(HM)$ である。縦方向の連続な散らかっていないマスの数も同様の手順で求められる。 $L(i,j)$ の計算量は $O(HM)$ である。

計算量

前処理は $O(HM)$ 、条件を見たす照明の置き方は $O(HM\log_2HM)$ となる。

私の提出は言語C++ (GCC 9.2.1)で実行時間591 msであった。この計算量はやや厳しいので、2の累乗を前計算して計算量を $O(HM)$ にすると良いだろう。

実装

#include <algorithm>
#include <atcoder/modint>
#include <iostream>
using namespace atcoder;
using namespace std;
#define int long long
using mint = modint1000000007;

// 散らかっていないマスを数える
int countUnclutteredMasses(const vector<string> &s) {
    int count = 0;
    for (auto &&si : s) {
        for (auto &&sij : si) {
            if (sij == '.') count++;
        }
    }

    return count;
}

// 照明が置かれたとき、マス(i,j)を照らすマスを数える
vector<vector<int>> countLightMasses(const vector<string> &s) {
    const int h = s.size(), w = s.front().size();

    // 数えた数を保存する二次元配列
    vector<vector<int>> t(h, vector<int>(w, 0));

    // 各列ごとに数える
    for (int i = 0; i < h; i++) {
        vector<int> line(w, 0);
        for (int j = 0; j < w; j++) {
            if (j == 0) {
                if (s[i][j] == '.') line[j] = 1;
                continue;
            }

            if (s[i][j] == '.') line[j] = line[j - 1] + 1;
        }
        for (int j = w - 1; j >= 0; j--) {
            if (j == w - 1) continue;
            if (s[i][j] == '.') line[j] = max(line[j], line[j + 1]);
        }

        for (int j = 0; j < w; j++) {
            t[i][j] += line[j];
        }
    }

    // 各行ごとに数える
    for (int j = 0; j < w; j++) {
        vector<int> line(h, 0);
        for (int i = 0; i < h; i++) {
            if (i == 0) {
                if (s[i][j] == '.') line[i] = 1;
                continue;
            }

            if (s[i][j] == '.') line[i] = line[i - 1] + 1;
        }
        for (int i = h - 1; i >= 0; i--) {
            if (i == h - 1) continue;
            if (s[i][j] == '.') line[i] = max(line[i], line[i + 1]);
        }

        for (int i = 0; i < h; i++) {
            t[i][j] += line[i];
        }
    }

    // 重複して数えた分を引く
    for (auto &&ti : t) {
        for (auto &&tij : ti) {
            tij--;
        }
    }

    return t;
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    for (int i = 0; i < h; i++) cin >> s[i];

    // Kを数える
    const int k = countUnclutteredMasses(s);

    // 照明が置かれたとき、マス(i,j)を照らすマスを数える
    auto t = countLightMasses(s);

    mint ans;

    // 各マス毎に条件を満たす照明の置き方を数え上げる
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (s[i][j] != '.') continue;

            const int l = t[i][j];

            ans += (mint(2).pow(l) - 1) * mint(2).pow(k - l);
        }
    }

    cout << ans.val() << "\n";
}

感想

実装重視問題かな。 $L(i,j)$ を求めるのはD - Lampと同じ。ともあれコンテスト中に解けてよかった。