yukicoder : No.348 カゴメカゴメ

遅れて参加したけど、解けて良かった。
http://yukicoder.me/problems/795

問題

N*Mのグリッドがある。
一部のマスは埋まっており、埋まっているマスのうち八近傍で隣接するもの同士を連結すると、輪を構成する。
輪は互いに交差することがない。

各々の輪は、使用する・しないを選ぶことができる。
ただし、使用する輪のすぐ外側にある輪は使用できない。

最適な輪の選択をしたとき、使用する輪に含まれるマス総数の最大値を求めよ。

解法

まず、輪とその輪に直接(間に他の輪が挟まることなく)囲まれた輪を親子関係と見なし、全ての輪を根付き木として表現しよう。
色んな解法があるだろうが、自分は以下のようにした。

まずUnion-Findを用いて、輪及び空きマスの連結関係を求める。

• 埋まったマスについては、８近傍の埋まったマスを連結する。
• 空きマスについては、４近傍の空きマスを連結する。

この際、グリッド全体を外側１周空きマスで囲っておくと、一番外側は必ず空きマスであることが仮定できるの後が楽になる。

後は一番外側のマスから「その連結マス群に隣接する、未訪問の異なる種類のマス」をDFSで辿ると、親から空→埋→空→埋…の順番で輪を外から内側にたどることができる。
この木の頂点を親から１つとばしに見れば、埋まったマス群、すなわち輪の親子関係がわかる。

あとは輪の親子関係に対して木DPをする。
以下の２値をDFSで葉から順に求めていこう。

• その輪を選択しない場合の、subtree内の使用する輪のマス総数の最大値
• その輪を選択する場合の、（同上）

int H,W;
string S[1010];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

UF<1010101> uf;
vector<int> C[1010*1010];
vector<int> G[1010*1010];
int vis[1010*1000];
int dp[1010*1000][2];


void dfs(int c,int ph) {
	int sy=c/W;
	int sx=c%W;
	vis[c]=1;
	int i,tx,ty;
	
	FORR(r,G[c]) {
		int cy=r/W,cx=r%W;
		for(ty=max(0,cy-1);ty<=min(cy+1,H-1);ty++) for(tx=max(0,cx-1);tx<=min(cx+1,W-1);tx++) if(vis[uf[ty*W+tx]]==0 && S[ty][tx]!=S[sy][sx]) {
			dfs(uf[ty*W+tx],1-ph);
			if(ph==0) {
				C[sy*W+sx].push_back(uf[ty*W+tx]);
			}
			else {
				FORR(r2,C[uf[ty*W+tx]]) C[sy*W+sx].push_back(r2);
			}
		}
	}
}

int dfs2(int r) {
	dp[r][1]=uf.count(r);
	FORR(r2,C[r]) {
		dfs2(r2);
		dp[r][0]+=max(dp[r2][0],dp[r2][1]);
		dp[r][1]+=dp[r2][0];
	}
	return max(dp[r][0],dp[r][1]);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	
	FOR(y,H) cin>>S[y+1], S[y+1]="."+S[y+1]+".";
	H+=2;
	W+=2;
	S[0]=string(W,'.');
	S[H-1]=string(W,'.');
	
	FOR(y,H) FOR(x,W) {
		for(i=-1;i<=1;i++) for(j=-1;j<=1;j++) if((i==0 || j==0) || S[y][x]=='x') 
			if(y+i>=0 && y+i<H && x+j>=0 && x+j<W && S[y+i][x+j]==S[y][x]) uf(y*W+x,(y+i)*W+(x+j));
	}
	FOR(y,H) FOR(x,W) G[uf[y*W+x]].push_back(y*W+x);
	dfs(uf[0],0);
	
	int ret=0;
	FORR(r,C[uf[0]]) ret += dfs2(r);
	cout<<ret<<endl;
}

まとめ

幸い今回4問ともWAは出ませんでした。