hotaruの蛍雪日記

競プロとゲームをしています

E - Lamps HHKB2020

f:id:hotarunx:20201023150708j:plain

問題情報

問題へのリンク 解説へのリンク

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
..####..
....##..

f:id:hotarunx:20201023145943j:plain

①は赤線で囲んだ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. j=0から順に次の漸化式で A(i,j)を更新する。
    1. マス(i,j)が散らかっていないならばA(i,j)=A(i,j-1)+1
    2. マス(i,j)が散らかっているならばA(i,j)=0

f:id:hotarunx:20201023150028j:plain

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

f:id:hotarunx:20201023150040j:plain

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と同じ。 ともあれコンテスト中に解けてよかった。