問題概要

$N \times N$ のグリッドが与えられる。各マスには文字 'o' または 'x' が描かれている。これらのマスから 3 個選ぶ方法であって、

3 マスに書かれた文字はすべて 'o' である
3 マスのうち、ちょうど 2 マスが同じ行にある
3 マスのうち、ちょうど 2 マスが同じ列にある

という条件を満たすものの個数を求めよ。

制約

$1 \le N \le 2000$

考えたこと

3 マスすべてを探索すると $O(N^{6})$ の計算量となって到底間に合わない。そこで、ある量を固定できないかを考えてみよう。

ここでは、3 マスが L 字の形になっていることに注目して、L 字の真ん中を固定して考えることにしよう。そうすると、たとえば下図のように、ある特定のマスを「L 字の真ん中のマス」として固定したときに、

そのマスと同じ行のマスのうち、'o' のマスを 1 つ選ぶ
そのマスと同じ列のマスのうち、'o' のマスを 1 つ選ぶ

という方法が、問題文の条件を満たす「L 字をなす 3 マス」にぴったり対応する。

ここで、あらかじめ次の情報を求めておこう。

yoko[i] ← $i$ 行目の 'o' の個数
tate[j] ← $j$ 列目の 'o' の個数

そうしたときに、この問題は、次のように解ける。各マス $(i, j)$ について、それが 'o' であるときに、

(yoko[i] - 1) * (tate[j] - 1)

の値を合算していく。「-1」をしているのは、その行や列の 'o' の個数からマス $(i, j)$ 自体を除外するためだ。

この方法によって、全体で $O(N^{2})$ の計算量で解ける。

コード

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

int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    for (int i = 0; i < N; ++i) cin >> S[i];
    
    vector<int> yoko(N, 0), tate(N, 0);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (S[i][j] == 'o') {
                ++yoko[i];
                ++tate[j];
            }
        }
    }
    
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (S[i][j] == 'o') {
                res += (yoko[i] - 1) * (tate[j] - 1);
            }
        }
    }
    cout << res << endl;
}

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

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

AtCoder ABC 330 D - Counting Ls (茶色, 400 点)

問題概要

制約

考えたこと

コード