kmjp's blog

競技プログラミング参加記です

TopCoder SRM 623 Div1 Easy UniformBoard、Div2 Hard ApplesAndPears

SRM

SRM623は不参加。出てたらEasy早解きでレート微増してたかな。
MediumはTLでヒントを見てしまったので、見てなかったら本番解けたか不明。
今回はDiv2 HardがDiv1 Easyの少し難しい問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13209
http://community.topcoder.com/stat?c=problem_statement&pm=12807

問題

NxNのグリッドがある。
各グリッドは初期状態で空・リンゴが置いてある・梨が置いてある、のいずれかである。

ここでリンゴまたは梨を１つ選び、空のマスに移す、という処理を最大K回行える。
この時、グリッド上の矩形領域のうち以下の条件を満たす最大面積を答えよ。

  • Div1 Easy ：矩形内の全マスがリンゴである。
  • Div2 Easy ：矩形内の全マスが同じ状態(リンゴ or 梨 or 空)である。

解法

前提として、空マスが１つはないと何も移動できない。空マスが0個の時は、K=0と考えると良い。

それ以外の場合、矩形内をすべて同じ種類にするには以下の手数がかかる。

  • 全マスリンゴにする：梨を矩形外の空マスに追い出し、その後空マスにリンゴを埋めるので、矩形内の（梨の数×２＋空の数）の手数分かかる。
  • 全マス梨にする：上記推論をリンゴと梨を逆にすると、矩形内の（リンゴの数×２＋空の数）の手数分かかる。
  • 全マス空にする：矩形内の（リンゴの数＋梨の数）の手数分かかる。

空マスは１個でもあれば常に上記の手順が取れる。
矩形内への移動と矩形外の移動のうち常に片方はできるし、片方を行うと次は逆方向の移動ができるはずであり、結局必要な移動は(順番さえ工夫すれば)出来ることになる。

上記推論より、グリッド上の全矩形領域を総当たりし、矩形内のリンゴ・梨・空のマスを求めて、K手以下で全マスリンゴ・梨・空出来る場合、その面積の最大値を更新していけばよい。

矩形の列挙の計算量はO(N^4)である。
Div1 EasyはN<=20と小さいので、矩形内の各マスのカウントにO(N^2)かけ、全部でO(N^6)かけても間に合う。
Div2 HardはN<=50でO(N^6)では間に合わないので、事前に累積和を使って矩形内のマスカウントをO(1)で終えられるようにしておく必要がある。

以下、Div1 EasyとDiv2 Hardのコードは同じで、Div2 Hardは梨や空マスで埋まった矩形を許可する点のみ異なる。

class UniformBoard {
	int NA[52][52],NP[52][52],NE[52][52];
	public:
	int getBoard(vector <string> board, int K) {
		int N=board.size();
		int x,y,h,w,h2;
		int ret=0;
		
		ZERO(NA);
		ZERO(NP);
		ZERO(NE);
		FOR(y,N) FOR(x,N) {
			FOR(h,y+1) NA[y+1][x+1]+=count(board[h].begin(),board[h].begin()+x+1,'A');
			FOR(h,y+1) NP[y+1][x+1]+=count(board[h].begin(),board[h].begin()+x+1,'P');
			FOR(h,y+1) NE[y+1][x+1]+=count(board[h].begin(),board[h].begin()+x+1,'.');
		}
		if(NE[N][N]==0) K=0;
		FOR(y,N) FOR(x,N) for(h=1;y+h<=N;h++) for(w=1;x+w<=N;w++) {
			if(h*w<=ret) continue;
			int CA=NA[y+h][x+w]-NA[y+h][x]-NA[y][x+w]+NA[y][x];
			int CP=NP[y+h][x+w]-NP[y+h][x]-NP[y][x+w]+NP[y][x];
			int CE=NE[y+h][x+w]-NE[y+h][x]-NE[y][x+w]+NE[y][x];
			if(NA[N][N]>=h*w && CE+CP*2<=K) ret=h*w;
		}
		return ret;
	}
}

class ApplesAndPears {
	public:
	int NA[52][52],NP[52][52],NE[52][52];
	
	int getArea(vector <string> board, int K) {
		int N=board.size();
		int x,y,h,w,h2;
		int ret=0;
		
		ZERO(NA);
		ZERO(NP);
		ZERO(NE);
		FOR(y,N) FOR(x,N) {
			FOR(h,y+1) NA[y+1][x+1]+=count(board[h].begin(),board[h].begin()+x+1,'A');
			FOR(h,y+1) NP[y+1][x+1]+=count(board[h].begin(),board[h].begin()+x+1,'P');
			FOR(h,y+1) NE[y+1][x+1]+=count(board[h].begin(),board[h].begin()+x+1,'.');
		}
		if(NE[N][N]==0) K=0;
		FOR(y,N) FOR(x,N) for(h=1;y+h<=N;h++) for(w=1;x+w<=N;w++) {
			if(h*w<=ret) continue;
			int CA=NA[y+h][x+w]-NA[y+h][x]-NA[y][x+w]+NA[y][x];
			int CP=NP[y+h][x+w]-NP[y+h][x]-NP[y][x+w]+NP[y][x];
			int CE=NE[y+h][x+w]-NE[y+h][x]-NE[y][x+w]+NE[y][x];
			
			if(NA[N][N]>=h*w && CE+CP*2<=K) ret=h*w;
			if(NP[N][N]>=h*w && CE+CA*2<=K) ret=h*w;
			if(NE[N][N]>=h*w && CA+CP<=K) ret=h*w;
		}
		return ret;
	}
}

まとめ

300ptのEasyの割には簡単かも。
Div1 Easyを解いておくと、Div2 Hardも簡単だね。