Codeforces #194 Div1. B. Chips

本番Aの題意がつかめず終盤でBに移ったけど時間切れした問題。
終了後に答え思いついた…。
http://codeforces.com/contest/333/problem/B

問題

N*Nのグリッド中、いくつか移動不可なマスがある。
この状態で、角以外の周辺マスにいくつかチップを置く。
各チップは反対側のマス（左端なら右端）に向けて、時間１当たり１マス動く移動する。
反対側に到着したら集合。

ここで、以下の条件のいずれかを満たしてしまうと負けとなる。

• 途中移動不可なマスをチップが通過する。
• 同じマスに２つ以上のチップが重なる。
• ２つのチップがすれ違う。

負けとならないように配置できる最大チップ数を答えよ。

解法

左端r行目、すなわち0列r行にあるチップを考える。
これが途中重なったりすれ違ったりする可能性のあるチップを考える。
それは対面の(N-1)列r行、上から来るr列0行、下から来る(N-1-r)列(N-1)行である。

同様にこれら３つのチップと重なる可能性のあるチップを列挙していくと、結局：

• 左端：r行・(N-1-r)行
• 右端：r行・(N-1-r)行
• 上端：r列・(N-1-r)列
• 右端：r列・(N-1-r)列

の８つが互いに干渉の可能性がある。
高々8つで置く・置かないの組み合わせは2^8通りなので、2^8通りのうち互いにぶつからない置き方を全列挙すればよい。
これを0<=r

int N,M;
int NGy[1001],NGx[1001];
int memo[1000];
int okok(int x1,int x2,int y1,int y2) {
	int mask=(3<<6)*x1+(3<<4)*x2+(3<<2)*y1+3*y2;
	int i;
	if(memo[mask]>=0) return memo[mask];
	memo[mask]=0;
	FOR(i,256) {
		if((mask & i) != i) continue;
		if((i&(1<<7)) && (i&(1<<6))) continue;
		if((i&(1<<5)) && (i&(1<<4))) continue;
		if((i&(1<<3)) && (i&(1<<2))) continue;
		if((i&(1<<1)) && (i&(1<<0))) continue;
		if((i&(1<<7)) && (i&(1<<3))) continue;
		if((i&(1<<7)) && (i&(1<<0))) continue;
		if((i&(1<<6)) && (i&(1<<2))) continue;
		if((i&(1<<6)) && (i&(1<<1))) continue;
		if((i&(1<<5)) && (i&(1<<2))) continue;
		if((i&(1<<5)) && (i&(1<<1))) continue;
		if((i&(1<<4)) && (i&(1<<3))) continue;
		if((i&(1<<4)) && (i&(1<<0))) continue;
		memo[mask]=max(memo[mask],__builtin_popcount(i));
	}
	return memo[mask];
}

void solve() {
	int f,i,j,k,l, x,y;
	ll r=0;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		NGx[x-1]=1;
		NGy[y-1]=1;
	}
	MINUS(memo);
	int res=0;
	for(x=1;x<N/2;x++) {
		res += okok(1-NGx[x],1-NGx[N-1-x],1-NGy[x],1-NGy[N-1-x]);
	}
	if(N%2==1) if(NGx[N/2]==0 || NGy[N/2]==0) res++;
	cout << res << endl;
	return;
}

まとめ

本番、ぶつかる可能性のあるチップ通しを列挙したら数が爆発するんじゃないかと迷った。
結局高々8個になることに早めに気づけばよかったな。