TopCoder SRM 594 Div2 Hard FoxAndGo2

今回のDiv2Hard、なんとか自力で解けたけどえらく実装が重いような。
http://community.topcoder.com/stat?c=problem_statement&pm=12809

問題

碁盤上にいくつか白石が置いてある。
ここに以下のルールに応じて黒石をおいていくことができる。

• 黒石を置いたとき、隣接した白石同士からなるグループが空白マスに接していない場合白石グループを取り除く。
• 黒石を置いたとき、白石グループが取り除けずにかつ隣接した黒石同士からなるグループが空白マスに接していない状態を作ってはならない。

上記条件を満たして黒石をとっていくとき、白石を最大何個取り除けるか答えよ。

解法

隣接する白石同士および空白マス同士をグループにしてみる。

ある白石グループを取り除ける条件は以下の通りである。

1. 白石グループに接する空白マスグループのうち、以下両方を満たすのが1つ以下である。
   1. 空白マスグループに接する白石グループがまだ1つも取り除かれてない。
   2. 空白マスグループ中のすべてのマスが取り除きたい白石グループに接している。

1-2の条件は、空白マスをすべて黒石で埋めないと白石を取り除けないことを示す。
ただ、1-1の条件により既に他の白石グループが1個でも取り除かれていれば、そこに空白ができるので空白マスをすべて黒石で埋めても問題ない。

また、空白マスをすべて黒石で埋めてしまっても、最後の黒石を埋めることで白石グループを取り除ければ問題ないので、すべて埋めないといけない空白マスが1個までなら存在してもよい。

上記事実を踏まえて、以下の順で処理していけばよい。

• まずDFSで隣接マスをたどり、白石および空白マスをグループ化する。
• 白石グループと空白マスグループを比べ、空白マスグループの全マスが白石グループに接するかチェックする(1-2の条件判定を行う)。すべて接する場合、白石グループに対して解消すべき空白マスグループとして記憶しておく。
• 初期状態は、全白石グループが未処理状態とする。以下の処理を状態が変化しなくなるまで行う。
  • 解消すべき空白マスグループが1つ以下の白石グループを探す。見つからなければループを抜ける。
  • 見つけた白石グループは取り除ける。また、その時白石グループに隣接する空白マスグループはすべて埋めても問題ないグループとなる。
  • 未処理の白石グループにおける解消すべき空白マスグループから、上記すべて埋めても問題ない空白マスグループを取り除く。

int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
int NB,NE;
set<int> bl[2501],em[2501],b2e[2501],b2el[2501];
int fr[2501][2501],fr2[2501];

class FoxAndGo2 {
	public:
	int boss[51][51],N;
	vector<string> B;
	
	void dfs(char c,int x,int y,int key,set<int>& ss) {
		int i,tx,ty,f=1;
		ss.insert(x*50+y);
		boss[x][y]=key;
		FOR(i,4) {
			tx=x+dx[i],ty=y+dy[i];
			if(tx<0 || tx>=N || ty<0 || ty>=N) continue;
			if(B[tx][ty]!=c) continue;
			if(boss[tx][ty]!=-1) continue;
			ss.insert(tx*50+ty);
			boss[tx][ty]=key;
			dfs(c,tx,ty,key,ss);
		}
	}
	
	int maxKill(vector <string> board) {
		B=board;
		N=B.size();
		MINUS(boss);
		NB=NE=0;
		
		int x,y,i,tx,ty;
		FOR(i,2500) bl[i].clear(),em[i].clear(),b2e[i].clear(),b2el[i].clear();
		FOR(x,N) FOR(y,N) if(boss[x][y]==-1 && B[x][y]=='o') dfs('o',x,y,NB,bl[NB]),NB++;
		FOR(x,N) FOR(y,N) if(boss[x][y]==-1 && B[x][y]=='.') dfs('.',x,y,NE,em[NE]),NE++;
		if(NB==0) return 0;
		
		FOR(x,NB) FOR(y,NE) {
			fr[x][y]=0,fr2[y]=0;
			ITR(it,em[y]) {
				int ex=*it/50,ey=*it%50;
				int f=1;
				FOR(i,4) {
					tx=ex+dx[i],ty=ey+dy[i];
					if(tx<0 || tx>=N || ty<0 || ty>=N) continue;
					if(B[tx][ty]=='o' && boss[tx][ty]==x) f=0;
				}
				fr[x][y]|=f;
			}
		}
		
		FOR(x,N) FOR(y,N) if(B[x][y]=='o') {
			FOR(i,4) {
				tx=x+dx[i],ty=y+dy[i];
				if(tx<0 || tx>=N || ty<0 || ty>=N) continue;
				if(B[tx][ty]=='.' && fr[boss[x][y]][boss[tx][ty]]==0) b2e[boss[x][y]].insert(boss[tx][ty]);
				if(B[tx][ty]=='.') b2el[boss[x][y]].insert(boss[tx][ty]);
			}
		}
		set<int> cand;
		FOR(i,NB) cand.insert(i);
		int r=0;
		int up=1;
		while(up) {
			up=0;
			ITR(it,cand) if(b2e[*it].size()<=1) {
				up=1;
				x=*it;
				cand.erase(it);
				r+=bl[x].size();
				ITR(ite,b2el[x]) ITR(it2,cand) b2e[*it2].erase(*ite);
				break;
			}
		}
		return r;
	}
};

まとめ

Div2 Hardとはいええらく実装が重い問題。
何とか自分で解ききれてよかった。
Div1 Mediumと全然解答が異なるのが面白いね。