SRM 623 DIV1 Easy - UniformBoard （○）

November 02, 2014

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13209&rd=15856

・N×Nのボードが与えられる。
・ボードの各セルには空白、apple,pearいずれかが置かれている。
・また、１回の操作でappleかpearを空白に移すことができる。
・最大の操作回数はKで、任意の長方形の中のセルがすべてappleであるようなときの
　最大の長方形の面積を求める。

解き方

・すべての長方形で検索すればよさそう。
・長方形を作ったとき、そもそも全体のappleより大きいセルは作れないので
　最初にすべてのappleの数を調べる必要がある。
・長方形を作ったときにpearが含まれているとき、空白が一つもないと移せないので
　最初に空白があるかどうかを調べる必要がある。
・空白は１回の操作でappleを置くことができるが、pearは一回どかしてからappleを置く必要が
　あるので２回の操作が必要。

・よって任意の長方形を考えた時、セルの数が全体のapple以下かつ、
　pearもしくは空白が含まれていないか、空白の数＋pearの数×２＜＝Kかつ空白が全体に
　存在するときはその長方形をすべてappleにできる。

→System Passed.

コード

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class UniformBoard {

public: int getBoard(vector<string> board, int K) {
int n=board.size();

int a=0,b=0;
FORE(i,0,n)FORE(j,0,n){
if(board[i][j]=='A')a++;
if(board[i][j]=='.')b=1;
}

int ret=0;
FORE(i,0,n)FORE(j,0,n)FORE(k,i,n)FORE(l,j,n){
int cnt=(k-i+1)*(l-j+1);
if(cnt>a)continue;
int curb=0,curp=0;
FORE(x,i,k+1)FORE(y,j,l+1){
if(board[x][y]=='P')curp++;
if(board[x][y]=='.')curb++;
}
if((curb==0&&curp==0) ||(curb+curp*2<=K && b))ret=max(ret,cnt);
}

return ret;
}

};

カバー