TopCoder SRM 611 Div2 Hard ElephantDrinkingEasy

Div2 Hardとしては簡単な方。
http://community.topcoder.com/stat?c=problem_statement&pm=13039

問題

最大5x5のグリッドがあり、いくつかのセルに水たまりがある。
グリッドを囲む辺上に、それぞれ5マス×4辺分の象がいる。
各象は辺に垂直に鼻を伸ばし、水たまりの水を飲むことができる。
ただし、他の象の鼻とぶつかってはならない。

最大何匹の象が水を飲めるか。

解法

各象、辺より遠い水を飲む必要性はないので、最寄の水たまりの水を飲むものとする。
すると各象の鼻の長さが確定するので、各象が同時に水を飲もうとするとぶつかるかどうか判定できる。

象の数は高々20匹なので、bitmaskで水を飲める象を列挙し、互いにぶつからない組み合わせで象が最多となるものを探せばよい。

class ElephantDrinkingEasy {
	public:
	int maxElephants(vector <string> M) {
		int N=M.size();
		int ok[4][5]; // 0-l 1-r 2-u 3-b
		int col[21][21]; // 0-l 1-r 2-u 3-b
		int y,x;
		
		MINUS(ok);
		ZERO(col);
		FOR(y,N) {
			FOR(x,N) if(M[y][x]=='Y') {
				if(ok[0][y]==-1) ok[0][y]=x;
				ok[1][y]=x;
			}
			col[y][N+y]=(ok[0][y]==ok[1][y]);
		}
		FOR(x,N) {
			FOR(y,N) if(M[y][x]=='Y') {
				if(ok[2][x]==-1) ok[2][x]=y;
				ok[3][x]=y;
			}
			col[x+N*2][x+N*3]=(ok[2][x]==ok[3][x]);
		}
		FOR(y,N) FOR(x,N) {
			if(ok[0][y]>=x && ok[2][x]>=y) col[y][N*2+x]=1;
			if(ok[0][y]>=x && ok[3][x]<=y) col[y][N*3+x]=1;
			if(ok[1][y]<=x && ok[2][x]>=y) col[y+N][N*2+x]=1;
			if(ok[1][y]<=x && ok[3][x]<=y) col[y+N][N*3+x]=1;
		}
		int r=0,mask;
		FOR(mask,1<<(4*N)) {
			int ng=0;
			if(r>=__builtin_popcount(mask)) continue;
			FOR(x,N) FOR(y,4) if((mask & (1<<(y*N+x))) && (ok[y][x]<0)) ng++;
			FOR(x,4*N) for(y=x+1;y<4*N;y++) {
				if((mask & (1<<x))==0) continue;
				if((mask & (1<<y))==0) continue;
				if(col[x][y]) ng++;
			}
			if(ng==0) r=__builtin_popcount(mask);
		}
		return r;
	}
};

まとめ

実際には、左右の辺上の象だけ列挙すれば、上下の象が水飲める飲めないが確定するので、もっと計算量を落とすことができる。