【AtCoder】ABC307 C - Ideal Sheet

遅すぎるかも。

解法

シートA, Bは少なくとも1つ以上の黒いマスを含み、そのマスは必ずシートXのいずれかの黒いマスに対応する。

よって、それぞれのシートから1マスずつ選び、シートXのどのマスに対応するかを全探索し、シートXのそれぞれの黒いマスに対応するシートA, Bいずれかの黒いマスが存在するかを判定すれば、全探索は $O(H_{X}^{2} W_{X}^{2} )$ で、判定は $O(H_{X} W_{X} )$ で、合計で $O(H_{X}^{3} W_{X}^{3} )$ できる。

実装

AtCoder への提出

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

#define REP(i, n) for (int i = 0; i < (n); i++)

pair<int, int> f(vector<string>& S) {
    REP(i, S.size()) REP(j, S[i].size()) {
        if (S[i][j] == '#') {
            return {i, j};
        }
    }
}

int count(vector<string>& S) {
    int res = 0;
    REP(i, S.size()) REP(j, S[i].size()) res += S[i][j] == '#';
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int HA, WA;
    cin >> HA >> WA;
    vector<string> A(HA);
    REP(i, HA) cin >> A[i];

    int HB, WB;
    cin >> HB >> WB;
    vector<string> B(HB);
    REP(i, HB) cin >> B[i];

    int HX, WX;
    cin >> HX >> WX;
    vector<string> X(HX);
    REP(i, HX) cin >> X[i];

    auto [ia, ja] = f(A);
    auto [ib, jb] = f(B);

    auto oka = [&](int x, int y) -> int { return 0 <= x and x < HA and 0 <= y and y < WA and A[x][y] == '#'; };
    auto okb = [&](int x, int y) -> int { return 0 <= x and x < HB and 0 <= y and y < WB and B[x][y] == '#'; };
    int ans = 0;
    int ca = count(A), cb = count(B);
    REP(i1, HX) REP(j1, WX) {
        if (X[i1][j1] != '#') continue;
        REP(i2, HX) REP(j2, WX) {
            if (X[i2][j2] != '#') continue;
            int ok = 1, cnt = 0;
            REP(i, HX) REP(j, WX) {
                if (X[i][j] != '#') continue;
                ok &= oka(ia + i - i1, ja + j - j1) or okb(ib + i - i2, jb + j - j2);
                cnt += oka(ia + i - i1, ja + j - j1) + okb(ib + i - i2, jb + j - j2);
            }
            ans |= ok and cnt == ca + cb;
        }
    }
    cout << (ans ? "Yes" : "No") << '\n';
    return 0;
}

感想

シートCのサイズがどのくらいかを考える必要がないのがこの解法の優れたところであるように思う。（この部分の見積もりを間違えて通せない人を何人か確認したため。）