ABC 278

Table of Contents

E - Grid Filling

https://atcoder.jp/contests/abc278/tasks/abc278_e

$\mathrm{ rows }(i, m)$ を 行番号が $[0,i)$ の範囲(0-index)での数字 $m$ の出現回数、$\mathrm{ cols }(j,m)$ を列番号が $[0,i)$ の範囲での数字 $m$ の出現回数とする。

$[i,i+h)$, $[j,j+w)$ の領域が塗りつぶされたときに、残りのマスに数字 $m$ の出現する場合以下の式の少なくとも1つが true となる。

\begin{align} &\mathrm{ cols }(j-1,m) > 0 \\ &\mathrm{ cols }(W,m) - \mathrm{ cols }(j+w-1,m)) > 0 \\ &\mathrm{ rows }(i-1,m) > 0 \\ &\mathrm{ rows }(H, m) - \mathrm{ rows }(i+h-1,m) > 0 \end{align}

出現する数字は $[1,300]$ の範疇なので愚直に全通り出現するか確認し、出現した数の種類数を出力する。

void solve() {
    ll H, W, N, h, w;
    cin >> H >> W >> N >> h >> w;
    vvll A(H + 1, vll(W + 1, 0));
    rep(i, H) rep(j, W) cin >> A[i + 1][j + 1];

    int sz = 301;
    vvll rows(H + 1, vll(sz, 0)), cols(W + 1, vll(sz, 0));
    rep(i, H) {
        rep(j, W) {
            rows[i + 1][A[i + 1][j + 1]]++;
            cols[j + 1][A[i + 1][j + 1]]++;
        }
    }

    rep(i, H) {
        rep(j, sz) {
            rows[i + 1][j] += rows[i][j];
        }
    }
    rep(i, W) {
        rep(j, sz) {
            cols[i + 1][j] += cols[i][j];
        }
    }

    for (int i = 1; i <= H - h + 1; i++) {
        for (int j = 1; j <= W - w + 1; j++) {
            ll cnt = 0;
            rep(k, sz) {
                bool t = false;
                t = t || cols[j - 1][k] > 0;
                t = t || (cols[W][k] - cols[j + w - 1][k] > 0);
                t = t || rows[i - 1][k] > 0;
                t = t || (rows[H][k] - rows[i + h - 1][k]) > 0;
                cnt += t;
            }

            if (j != 1)
                cout << ' ';
            cout << cnt;
        }
        cout << endl;
    }
}