TopCoder SRM605: AlienAndGame

任意の行は、自由に全体反転することができる。このことから、内部のそれぞれの行にはたかだか一色しか含まれていない正方形のうち、最大のサイズのものを求めれば良いことになる。

以下のコードでは、最大正方形を O(WH) で求める動的計画法のアルゴリズムを改造したものを適用している。

dp[row,col] = (row,col) を一番右下のセルとするような一色にできる正方形の最大サイズ

としたとき、dp[row,col] それぞれについて、壁があるわけではないので、少なくてもサイズ１の正方形が作れることは保証される。

そして、L = min(dp[row-1,col-1],dp[row,col-1],dp[row-1,col]) としたとき、L >= 2 の場合、それぞれの座標に対応する３つの正方形は領域が重なり合っているため、これらの正方形の和集合の領域を一色にできることが保証される。これに(row,col)と(row,col-1)の色が同じであるという条件が加わると、サイズ L + 1 の正方形が一色にできるということが言える。
L=1 のときは、領域が重なりあっていないため、「(row,col)と(row,col-1)の色が同じ」という条件に加えて、「(row-1,col)と(row-1,col-1)」の色が同じという条件が必要になる。この条件を入れなくてもサンプルが全て通るので注意。これで1WAしてしまった。

これで計算量はO(WH)だが、もっと素直な方法でO((WH)^2)で解くこともできる。

public class AlienAndGame {
    public int getNumber(string[] board) {
        int w = board[0].Length;
        int h = board.Length;
        var a = new int[h, w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                a[i, j] = 1;
                if (j - 1 >= 0 && i - 1 >= 0 && board[i][j] == board[i][j - 1] && board[i - 1][j] == board[i - 1][j - 1]) {
                    a[i, j] = new[] { a[i - 1, j - 1], a[i - 1, j], a[i, j - 1] }.Min() + 1;
                }
            }
        }
        var maxv = a.Cast<int>().Max();
        return maxv * maxv;
    }
}