TopCoder SRM 610 Div1 Easy TheMatrix [1人競技プログラミング Advent Calendar 2016 10日目]

昨日寝落ちしながら解法を生み出していた。

この記事は1人競技プログラミング Advent Calendar 2016 10日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement
白と黒のマスのグリッドが与えられる。
任意の四角形のグリッドを切り抜くことが出来る。
切り抜いた際に四角形のグリッドの全てのマスが「隣接マスが自身のマスと違う色である」という条件を満たしている必要がある。
上記の条件を満たした上で、最も大きく切り抜けるマスの数の個数を答えよ。

解いた方法：
下から累積和して
memo[i][j] = j列目のi行目のマスからスタートした際に、j列で取れるマスの個数
を保持しておく。

全てのマスからスタートし、列を増やすごとに作る事の出来る四角形の最大サイズをほぼO(1)で計算することが出来るようになる。

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

int memo[101][101];

class TheMatrix {
    public:
    vector<string> board;
    int MaxArea(vector<string> _board) {
        board = _board;
        REP(i, 101) REP(j, 101) memo[i][j] = 0;

        REP(i, board[0].length()){
            memo[board.size()-1][i] = 1;
        }

        for(int i=(int)board.size()-2; i>=0; i--){
            REP(j, board[0].length()){
                if(board[i+1][j] == board[i][j]) memo[i][j] = 1;
                else memo[i][j] = memo[i+1][j] + 1;
            }
        }

        int ans = 0;
        REP(i, board.size()){
            REP(j, board[0].length()){
                int min_cnt = memo[i][j];
                REP2(k, j, board[0].length()){
                    if(k != j && board[i][k-1] == board[i][k]) break;
                    min_cnt = min(min_cnt, memo[i][k]);
                    ans = max(ans, min_cnt * (k-j+1));
                }
            }
        }


        return ans;
    }
};