TopCoder SRM 578 Div1 Easy GooseInZooDivOne

さてSRM578。Easyをそこそこの速度で解けたけどMediumを解ききれずレートは微増。
Mediumは終了後ノーヒントで解けたので勿体なかったな。
http://community.topcoder.com/stat?c=problem_statement&pm=12539

問題

50x50のマス目状に、鳥のいる位置が与えられる。
鳥のいる位置にはガチョウかアヒルがいるが、このときガチョウは以下の条件を満たさなければならない。

• ガチョウは１羽以上・偶数羽いる。
• ガチョウからマンハッタン距離でDマス以内の鳥はガチョウである。

このようなガチョウの配置の組み合わせ数を答えよ。

解法

まず、距離の制約から１か所ガチョウを選ぶと連鎖的に距離D以内の鳥はガチョウになる。
よってこのようなまとめてガチョウになる組を先に求める。
ここではUnion-findを使ったが、単にBFSで探しても十分のようだ。

そして偶数羽の塊がA個と奇数羽の塊がB個で来たとする。
偶数羽の塊はそれぞれガチョウでもアヒルでもいいので2^A通り。
奇数羽の塊は、ガチョウ合計数が偶数になればいいので2^(B-1)通り。(これは最初の(B-1)組を任意に選び、最後の１組は合計が偶数に選ぶように取る、と考えられる)

ここから１つも選ばない場合を引くと、2^(A+B-1) - 1が答え。
本番の時は最後の組み合わせ数はDPでやったけど、こちらの方が楽だね。

なお、Div2 Mediumでは偶数縛りが無いので、奇数羽の塊の選び方は2^Bとなる点が異なる。

const int ufmax=10001;
int ufpar[ufmax],ufrank[ufmax];
void UF_init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; } }
int UF_find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = UF_find(ufpar[x]));}
void UF_unite(int x,int y) {
	x = UF_find(x); y = UF_find(y);
	if(x==y) return;
	if(ufrank[x]<ufrank[y]) ufpar[x]=y;
	else {ufpar[y]=x; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
}

ll mo=1000000007;

class GooseInZooDivOne {
	int W,H;
	public:
	int count(vector <string> field, int dist) {
		int y1,y2,x1,x2;
		
		H=field.size();
		W=field[0].size();
		UF_init();
		
		FOR(y1,H) FOR(x1,W) {
			if(field[y1][x1]=='.') continue;
			for(y2=y1;y2<H;y2++) FOR(x2,W) {
				if(abs(y1-y2)+abs(x1-x2)>dist) continue;
				if(field[y2][x2]=='.') continue;
				UF_unite(100*y1+x1,100*y2+x2);
			}
		}
		map<int,int> M;
		FOR(y1,H) FOR(x1,W) {
			if(field[y1][x1]=='.') continue;
			M[UF_find(100*y1+x1)]++;
		}
		
		int even=0, odd=0;
		for(map<int,int>::iterator mit=M.begin();mit!=M.end();mit++) {
			if(mit->second%2==1) odd++;
			else even++;
		}
		
		ll res=1;
		while(even--) res=(res*2) %mo;
		if(odd--) while(odd--) res=(res*2) %mo;
		return (res+(mo-1))%mo;
		
	}
}

まとめ

Union-findは頑張りすぎたか。

この問題、「最低１羽はガチョウがいる」「ガチョウが偶数である」って縛りがあるけど、なんか問題をややこしくするためだけに作った文面みたいでイマイチだな。
特に偶数云々はDiv2 Mediumとの大きな違いで、おかげで若干難易度が上昇してるんだけど問題への必然性が感じられず、面白みがなかった。