TopCoderOpen 2014 Round1B Medium EllysScrabble

TCO R1Bは不参加。
後で解いたところ、MediumもHardも方針はあってたけどしょうもないミスで1WAした。
Easyは200ptだしMediumから復習。
http://community.topcoder.com/stat?c=problem_statement&pm=13118

問題

２次元グリッド上に羊と狼がいる。
狼が隣接マスをたどって羊のところに行けないよう、行と行または列と列の間にフェンスを建てたい。
最少で何個のフェンスを立てれば、どの羊も狼が到達不能になるか。

解法

グリッドサイズHxWがそれぞれ16以下とかなり小さい。
よって、行と行の間に入れるフェンスは2^(H-1)通り総当たりしてしまおう。

フェンスで区切られた各行の集合において、集合内で同じ列に羊と狼がいたらそのフェンス配置は不可。
そうでない場合、「羊がいるこの列と狼がいるこの列の間に１か所以上フェンスがなければならない」、という条件が多数生成できる。
これらの条件をすべて満たす最少フェンス数を求めればよい。

この最少フェンス数は最小フローなど解かなくても貪欲に見つけられる。
条件をフェンスの終端位置でソートし、最も左の終端位置の場所からおいていけばよい。
このあたりは蟻本のSaruman's Armyの解説が参考になる。

class WolvesAndSheep {
	public:
	int H,W;
	vector<string> S;
	
	int dodo(int mask) {
		string SS[17];
		int cg=0,i,x,y;
		int mat[16][16];
		ZERO(mat);
		SS[0]=S[0];
		FOR(i,H-1) {
			if(mask&(1<<i)) {
				SS[++cg] = S[i+1];
			}
			else {
				FOR(x,W) {
					if(S[i+1][x]=='.') continue;
					else if(SS[cg][x]=='.' || SS[cg][x]==S[i+1][x])
						SS[cg][x]=S[i+1][x];
					else return 1000;
				}
			}
		}
		
		set<pair<int,int> > S;
		FOR(i,cg+1) {
			FOR(y,W) {
				if(SS[i][y]=='S' || SS[i][y]=='W') {
					char cur=SS[i][y];
					char tar=(cur=='S')?'W':'S';
					for(x=y+1;x<W;x++) {
						if(SS[i][x]==cur) break;
						if(SS[i][x]==tar) {
							mat[y][x-1]=1;
							break;
						}
					}
				}
			}
		}
		
		int ret=0;
		int cx=0;
		while(cx<W) {
			int mi=100;
			for(x=cx;x<W;x++) FOR(y,W) if(mat[x][y]) mi=min(mi,y);
			if(mi>=100) break;
			ret++;
			cx=mi+1;
		}
		return ret;
	}
	
	int getmin(vector <string> field) {
		S=field;
		H=field.size();
		W=field[0].size();
		
		int y,x;
		int nw=0,ns=0;
		FOR(y,H) FOR(x,W) nw+=S[y][x]=='W',ns+=S[y][x]=='S';
		if(nw==0 || ns==0) return 0;
		
		int mi=1000,mask;
		FOR(mask,1<<(H-1)) mi=min(mi,__builtin_popcount(mask)+dodo(mask));
		return mi;
		
	}
};

まとめ

Hardよりも実装がめんどい。
結構みんなコード長めだね。