面白かった。単純にやると $O(H^{2}W^{2})$ なので、そこから計算量オーダーを 1 つ落とすことを考える。

問題概要

$H \times W$ のグリッドが与えられる。各マスには 0, 1, 2 のうちのいずれかの値が描かれている。

これらの $HW$ 個のマスのうちの 4 マスの組であって、以下の条件を満たすものの個数を求めよ。

4 マスは長方形をなす
4 マスの数値からなる集合は {0, 1, 2} となる

制約

$1 \le H, W \le 400$

考えたこと

こういうのはとりあえず愚直解法の計算量を見積もってみて、そこからどのくらい計算量を落とさないといけないのかを考えることにしよう。まず、長方形を全探索する場合、

$H$ 行から 2 行分を選ぶ
$W$ 列から 2 列分を選ぶ

とすることで $O(H^{2}W^{2})$ の計算量となる。これでは間に合わない (部分点がとれる) ので、オーダーを 1 個落とすことを考えよう。

行から 2 行選ぶ方法を固定

こういうときは、なにかを固定して、残りの個数を求める部分の計算量を減らせないかと考えるのが定石。ここでは行 2 個を固定してみる。行 2 個を固定したときに、列方向から 2 箇所選ぶ方法を $O(W)$ でできれば勝ち！！

そこで、行 2 個 ( $i$ 行目と $j$ 行目とする) を固定したとき、次のような配列を考えよう。

num[ bit ] := マス $(i, k)$ とマス $(j, k)$ の値からなる集合が bit であるような $k$ の個数

たとえば、 $(i, k)$ の値が 0 で、 $(j, k)$ の値が 2 であれば、bit = 5 (= (1<<0) | (1<< 2)) について num[bit]++; とする。つまり、 $W$ 列を、以下の 8 パターンに分類するということだ (実際には 6 パターン)。

2 マスの値からなる集合が {} の列 (これはない)
2 マスの値からなる集合が {0} となる列 (2 マスとも 0)
2 マスの値からなる集合が {1} となる列 (2 マスとも 1)
2 マスの値からなる集合が {2} となる列 (2 マスとも 2)
2 マスの値からなる集合が {1, 2} となる列 (片方が 1 で片方が 2)
2 マスの値からなる集合が {2, 0} となる列 (片方が 2 で片方が 0)
2 マスの値からなる集合が {0, 1} となる列 (片方が 0 で片方が 1)
2 マスの値からなる集合が {0, 1, 2} となる列 (これはない)

このように分けたとき、

bit1 | bit2 = {0, 1, 2} となるような bit1, bit2 の組すべてについて
num[ bit1 ] × num[ bit2 ] を合計していく

というふうにすれば OK。

コード

計算量は $O(H^{2}W)$ となって間に合う。

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

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<int>> fi(H, vector<int>(W, 0));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> fi[i][j];
        }
    }

    // bit で表されるやつが含まれないところを除去
    long long res = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = i+1; j < H; ++j) {
            vector<long long> num(8, 0);
            for (int k = 0; k < W; ++k) {
                int bit = (1<<fi[i][k]) | (1<<fi[j][k]);
                num[bit]++;
            }
            for (int b1 = 0; b1 < 8; ++b1) {
                for (int b2 = b1; b2 < 8; ++b2) {
                    if ((b1 | b2) == 7) {
                        res += num[b1] * num[b2];
                    }
                }
            }
        }
    }
    cout << res << endl;
}

別解：包除原理

包除原理を使っても解ける。以下の値を計算すればよい。

すべての長方形の個数
- 0 を含まない長方形の個数
- 1 を含まない長方形の個数
- 2 を含まない長方形の個数
+ 1 と 2 を含まない長方形の個数
+ 2 と 0 を含まない長方形の個数
+ 0 と 1 を含まない長方形の個数
- 0 と 1 と 2 を含まない長方形の個数 (実際にはこれは 0 個)

コード

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

int main() {
    int H, W;
    cin >> H >> W;
    vector<vector<int>> fi(H, vector<int>(W, 0));
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            cin >> fi[i][j];
        }
    }

    // bit で表されるやつが含まれないところを除去
    long long res = 0;
    for (int bit = 0; bit < (1<<3); ++bit) {
        int con = 0;
        for (int i = 0; i < 3; ++i) if (bit & (1<<i)) ++con;
        for (int i = 0; i < H; ++i) {
            for (int j = i+1; j < H; ++j) {
                long long num = 0;
                for (int k = 0; k < W; ++k) {
                    if (bit & (1<<fi[i][k])) continue;
                    if (bit & (1<<fi[j][k])) continue;
                    ++num;
                }
                if (con % 2 == 0) res += num*(num-1)/2;
                else res -= num*(num-1)/2;
            }
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

JOI 春合宿 2011 day1-1 Banner (難易度 6)

問題概要

制約

考えたこと

行から 2 行選ぶ方法を固定

コード

別解：包除原理

コード