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; } };