Codeforces #221 Div1. C. Circling Round Treasures

正答者がDより少ないが、理解してしまえばそこまでは難しくない。
本番中に解くのは難しいけどね…。
http://codeforces.com/contest/375/problem/C

問題

NxMのグリッドがある。
各セルは移動可能な通常セルの他、移動不可能なセルとしてお宝・爆弾・壁がある。
プレイヤーの初期位置およびお宝の価値がわかっているとする。

以下の条件を満たすよう移動する場合、得られる最大のお宝の価値を答えよ。

• プレイヤーは移動可能マス内を隣接マスをたどって移動し、最後に初期位置に戻る。
• 当然移動不可能マスは移動できない。
• 移動時に通った経路に囲まれたお宝は取得し、その価値を得る(価値が負であっても得なければならない)
• 移動時に爆弾を囲う経路を通ってはならない。
• 移動1マスにつき1だけコストがかかり、お宝の価値の総和からその分差し引かなければならない。

なお、N,Mは20以下、お宝と爆弾の数の総和Lは8以下である。

解法

考えることは2つある。

• お宝や爆弾を囲ったことをどう判定するか。
• どのお宝を囲うのが最適か。

前者は多角形ないの点の内包判定を使う。
すなわち、点からどこか1方向に半直線を引き、多角形を成す辺と奇数回交差したら内部にあるとみなす。
以下のコードでは、お宝・爆弾が(x,y)にある場合、その右側(x+i,y)と(x+i,y+1)の間に半直線を引くとする。
移動経路がこの間を通れば交差回数が偶奇反転する。

L<=8であることから、各物体を奇数回すれ違ったかどうかをbitmapで管理すると、状態数はN*M*2^Lになる。
この状態間でダイクストラ法で移動コストを最小化すればよい。

上記方法で、各物体を囲ったまたは囲わない場合の閉路の移動コストがわかる。
あとはそれぞれの移動に対し、爆弾を囲っていないかどうかを判定し、囲った分のお宝の価値を加算することでお宝の価値および移動コストが求められる。
この値を最大化したものが答え。

int H,W,O;
string S[50];
int SX,SY;
int ox[8],oy[8],oc[8];
int rm[20][20];
int cost[20][20][1<<10];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>H>>W;
	
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) if(S[y][x]=='S') SX=x,SY=y,S[y][x]='.';
		FOR(x,W) if(S[y][x]>='1' && S[y][x]<='8') ox[S[y][x]-'1']=x,oy[S[y][x]-'1']=y,O=max(O,S[y][x]-'0');
	}
	FOR(x,O) cin>>oc[x];
	FOR(y,H) FOR(x,W) if(S[y][x]=='B') ox[O]=x,oy[O]=y,oc[O]=-1<<20,O++;
	
	FOR(i,O) for(x=ox[i]+1;x<W;x++) rm[oy[i]][x] |= 1<< i;
	
	FILL_INT(cost,100000000);
	cost[SY][SX][0]=0;
	multimap<int,int> Q;
	Q.insert(make_pair(0,SY*20000+SX*1000));
	while(!Q.empty()) {
		int co = Q.begin()->first;
		int key=Q.begin()->second;
		Q.erase(Q.begin());
		int cx=(key/1000)%20,cy=(key/20000)%20,cm=key%1000;
		if(co != cost[cy][cx][cm]) continue;
		
		FOR(i,4) {
			int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
			int ty=cy+dy[i],tx=cx+dx[i],tm=cm;
			if(ty<0 || tx<0 || ty>=H || tx>=W) continue;
			if(S[ty][tx]!='.') continue;
			if(i==0) tm^=rm[cy][cx];
			if(i==1) tm^=rm[cy-1][cx];
			if(cost[ty][tx][tm] > co + 1) {
				cost[ty][tx][tm] = co + 1;
				Q.insert(make_pair(cost[ty][tx][tm], ty*20000+tx*1000+tm));
			}
		}
	}
	
	int ma=0;
	FOR(i,1<<O) {
		int co=-cost[SY][SX][i];
		FOR(x,O) if(i&(1<<x)) co += oc[x];
		ma=max(ma,co);
	}
	_P("%d\n",ma);
	
}

まとめ

交差判定を偶奇でbitmapで持たせる点が目新しかった。このテクは覚えておこう。
点の内外判定コードは書いたことあるけど、グリッドに適用することが思いつかなかった…。