AtCoder ABC 311 E - Defect-free Squares (水色, 475 点)

有名な DP をするか、二次元累積和 + 二分探索をするか

• 問題へのリンク

問題概要

のグリッドが与えられる。グリッドの各マスのうち、指定された 個のマスには穴があいている。その他のマスは穴があいていない。

グリッドに含まれる正方形であって、その内部に穴を含まないもの何個あるかを求めよ。

制約

• 
• 

解法 (1)：DP

正方形の右下マスの位置で場合分けして数えることにしよう。つまり、マス を右下マスとする正方形が何個あるかを考える。

これは簡単で、マス を右下マスとする正方形のうち、内部に穴を含まない最大の正方形の一辺の長さを とすると、マス を右下マスとする正方形はちょうど 個ある (一辺が の 個)。

よって、この問題は、マス を右下マスとする最大正方形を求める問題へと帰着された。実はこれは超有名問題だ。AOJ Course にもある！

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_A&lang=ja

マス を右下マスとする最大正方形を求める問題

各マス を右下マスとする最大正方形は、DP で求められるのだ。次の配列 dp を考えよう。

---

dp[i+1][j+1] ← マス を右下マスとする最大正方形の一辺の長さ

---

さて、そもそもマス に穴がある場合は dp[i+1][j+1] = 0 とすればよい。

それ以外の場合について、dp[i+1][j+1] の値を求めるために、次の 3 つの場合に分けて考えよう。これらの場合は重複する可能性はあるが、抜け漏れはないことに注意しよう。

---

• Case 1：マス を右下マスとする最大正方形の左上頂点が、黒色マスと接点をもつとき
• Case 2：Case 1 以外のうち、マス を右下マスとする最大正方形の上辺が、黒色マスが辺で接するとき
• Case 3：Case 1 以外のうち、マス を右下マスとする最大正方形の左辺が、黒色マスが辺で接するとき

---

Case 1、Case 2、Case 3 それぞれについて、マス を右下マスとする最大正方形の一辺の長さは dp[i][j] + 1、dp[i][j+1] + 1、dp[i+1][j] + 1 と表せる。

マス を右下マスとする最大正方形は、これら 3 つの場合の最小のものを取ってくればよい。つまり、

`dp[i+1][j+1] = min({dp[i][j], dp[i][j+1], dp[i][j+1]}) + 1;

となる。

以上で配列 dp が求められるので、それを集計することで答えが求められる。全体の計算量は となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 1 is NG, 0 is OK
    int H, W, N;
    cin >> H >> W >> N;
    vector<vector<int>> S(H, vector<int>(W, 0));
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        S[a][b] = 1;
    }
    
    // dp[i+1][j+1] := マス (i, j) を右下マスとする最大の正方形の一辺の長さ
    vector<vector<int>> dp(H+1, vector<int>(W+1, 0));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (S[i][j] == 0) {
                dp[i+1][j+1] = min({dp[i+1][j], dp[i][j+1], dp[i][j]}) + 1;
            }
        }
    }
    
    // 集計
    long long res = 0;
    for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) res += dp[i+1][j+1];
    cout << res << endl;
}

解法 (2)：二次元累積和 + 二分探索

各マス を右下マスとする最大正方形の一辺の長さを求める方針までは一緒だ。

その最大正方形の一辺の長さを求めるために、二分探索する別解も考えられる。その場合の計算量は となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    // 入力 (穴マスを 1 とする)
    int H, W, N;
    cin >> H >> W >> N;
    vector<vector<int>> A(H, vector<int>(W, 0));
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        A[a][b] = 1;
    }
    
    // 二次元累積和
    vector<vector<int>> S(H+1, vector<int>(W+1, 0));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            S[i+1][j+1] = S[i][j+1] + S[i+1][j] - S[i][j] + A[i][j];
        }
    }
    // 右下がマス (i, j)、長さが len である正方形領域の穴の個数
    auto calc_num = [&](int i, int j, int len) -> int {
        return S[i+1][j+1] - S[i+1-len][j+1] - S[i+1][j+1-len] + S[i+1-len][j+1-len];
    };
    
    // 集計
    long long res = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            // 二分探索
            int low = 0, high = min(i, j) + 2;
            while (high - low > 1) {
                int len = (low + high) / 2;
                if (calc_num(i, j, len) > 0) high = len;
                else low = len;
            }
            res += low;
        }
    }
    cout << res << endl;
}