mayoko’s diary

プロコンとかいろいろ。

SRM 494 div1 easy:Painting

昔の SRM は easy は簡単(と言いつつ少し迷いましたが)なのであんまり書く意味が無いような気もしないでもない。

解法

あるサイズ S で塗れるのであれば, それより小さいサイズでも塗ることが出来るのは明らかでしょう。このような単調性があるので, 二分探索で解けます。

あるサイズ S で塗りきることが出来るかどうかは, 以下のようにしてわかります。
ある座標 (i, j) を左上として塗ろうとしてるとすると, (r, c) (i <= r < i+S, j <= c < j+S) がすべて B でなければなりません。すべて B の時は, 塗り, そうでない時は塗らない, ということをすべての (i, j) について試します。これで最初の構想通り塗れていれば OK で, そうでなければ NG です。

この解法の計算量は, O(N^4 log N) だと思います。

bool ok(int x, vector<string> picture) {
    int N = picture.size(), M = picture[0].size();
    vector<vi> board(N, vi(M));
    for (int i = 0; i+x <= N; i++) for (int j = 0; j+x <= M; j++) {
        bool ok = true;
        for (int k = i; k < i+x; k++) for (int l = j; l < j+x; l++) {
            if (picture[k][l] == 'W') {
                ok = false;
                break;
            }
        }
        if (ok) {
            for (int k = i; k < i+x; k++) for (int l = j; l < j+x; l++) {
                board[k][l] = 1;
            }
        }
    }
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) {
        if (board[i][j] == 0 && picture[i][j] == 'B') return false;
    }
    return true;
}

class Painting {
public:
    int largestBrush(vector <string> picture) {
        int N = picture.size(), M = picture[0].size();
        int low = 1, high = min(N, M)+1;
        while (high - low > 1) {
            int med = (high+low) / 2;
            if (ok(med, picture)) low = med;
            else high = med;
        }
        return low;
    }
};