kmjp's blog

競技プログラミング参加記です

AtCoder ABC #243 : Ex - Builder Takahashi (Enhanced version)

ARC

考察はともかく実装がしんどい。
https://atcoder.jp/contests/abc243/tasks/abc243_h

問題

H*Wのグリッドが与えられる。
スタートマスとゴールマスが与えられている。
スタートマスに置いた駒を、4近傍の隣接マスをたどってゴールマスに到達できないようにしたい。

そのため、いくつか通行不可のマスを設けることを考える。
ただし一部のマスは通行不可のマスにできない。

駒をゴールマスに到達できないようにする最小マス数と、そのマスの選び方の組み合わせ数を答えよ。

解法

まずマス目であることを無視し、スタート地点とゴール地点を曲線で結ぶとき、曲線が通ってはいけないエリアを別の曲線で定めることで結べないようにすることを考える。
これには、通ってはいけないエリアを閉曲線とし、スタート・ゴールいずれかの地点だけをその閉曲線囲えば条件を満たす。
いずれかの地点だけを囲う条件を言い換えると、スタート地点とゴール地点を結んだ線を考え、閉曲線がその線を奇数回だけ横断していれば良い。

これをマス目で考えるとEditorialのようになる。
通行不可のマスを8近傍で考えたとき閉曲線となるように配置しよう。

スタート地点とゴール地点を最短で結ぶ経路上のセルを赤色のセル。赤色のセルに8近傍で右上側で接するセルを青色のセルとする。
通行不可のマスが赤色と青色のセルで(8近傍で)隣接する箇所が奇数箇所なら条件を満たす。
あとは、「通行不可マスを配置する最寄りの赤色マス」を総当たりしながら、組み合わせを計算していく。
その際は、総当たりする赤色マスの位置を(R,C)としたとき、
dp(r,c,p) := (R,C)から8近傍の隣接マスをたどって通行不可マスを置いてきたとき、最後(r,c)に通行不可マスを置いて、かつ赤青マスの横断回数のパリティがpであるときの、最小マス数とその組み合わせ
としてdp(R,C,0) := {0,1}から初めてdp(R,C,1)を求めよう。
上記処理では閉曲線を時計回り反時計回りで二重にカウントするので、組み合わせ数は最後に2で割る。

要注意すべきは、グリッドの外側も閉曲線に含むと考えることができ、かつ通行不可マス数を増やさないこと。
自分以外にもWAが3つだけ取れない人が散見されたけど、周辺部で通行不可マスが隣接するとき、グリッド外を通るケースと通らないケースで二重カウントしてないか確認しよう。

int H,W;
string C[155];

int cost[155][155];
int E[155][155];
int B[155][155],R[155][155];
const ll mo=998244353;
vector<vector<int>> T[155][155];
ll D[155][155][2];
ll dp[155][155][2];

pair<ll,ll> hoge(int sy,int sx) {
	int y,x;
	FOR(y,H+2) FOR(x,W+2) {
		D[y][x][0]=D[y][x][1]=1LL<<60;
		dp[y][x][0]=dp[y][x][1]=0;
	}
	
	D[sy][sx][0]=0;
	dp[sy][sx][0]=1;
	priority_queue<pair<ll,ll>> Q;
	Q.push({0,sy*10000+sx*10+0});
	while(Q.size()) {
		ll co=-Q.top().first;
		int cy=Q.top().second/10000;
		int cx=Q.top().second/10%1000;
		int num=Q.top().second%10;
		Q.pop();
		if(D[cy][cx][num]!=co) continue;
		FORR(t,T[cy][cx]) {
			int ty=t[0];
			int tx=t[1];
			int nnum=t[2]^num;
			if(D[ty][tx][nnum]>co+cost[ty][tx]) {
				D[ty][tx][nnum]=co+cost[ty][tx];
				Q.push({-D[ty][tx][nnum],ty*10000+tx*10+nnum});
				dp[ty][tx][nnum]=0;
				
			}
			if(D[ty][tx][nnum]==co+cost[ty][tx]) {
				(dp[ty][tx][nnum]+=dp[cy][cx][num])%=mo;
			}
		}
	}
	return {D[sy][sx][1],dp[sy][sx][1]};
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	int SY,SX,GY,GX;
	FOR(y,H) {
		cin>>C[y];
		FOR(x,W) {
			if(C[y][x]=='S') SY=y,SX=x;
			if(C[y][x]=='G') GY=y,GX=x;
		}
	}
	if(SX>GX) {
		FOR(y,H) reverse(ALL(C[y]));
		SX=W-1-SX;
		GX=W-1-GX;
	}
	if(SY>GY) {
		for(y=0;y*2<H;y++) swap(C[y],C[H-1-y]);
		SY=H-1-SY;
		GY=H-1-GY;
	}
	FOR(y,H) FOR(x,W) {
		if(C[y][x]=='.') cost[y][x]=1;
		else cost[y][x]=1<<20;
	}
	
	SY++,SX++,GY++,GX++;
	for(x=SX;x<=GX+1;x++) B[SY-1][x]=1;
	for(x=SX+1;x<=GX;x++) R[SY][x]=1;
	for(y=SY-1;y<=GY;y++) B[y][GX+1]=1;
	for(y=SY;y<=GY-1;y++) R[y][GX]=1;
	
	vector<pair<int,int>> edge;
	FOR(y,H) edge.push_back({y,0});
	FOR(y,H) edge.push_back({y,W-1});
	for(x=1;x<W-1;x++) edge.push_back({0,x});
	for(x=1;x<W-1;x++) edge.push_back({H-1,x});
	
	FOR(i,edge.size()) FOR(j,i) {
		int st=R[edge[i].first+1][edge[i].second+1]&&(edge[i].first==0||edge[i].second==W-1);
		st^=R[edge[j].first+1][edge[j].second+1]&&(edge[j].first==0||edge[j].second==W-1);
		T[edge[i].first][edge[i].second].push_back({edge[j].first,edge[j].second,st});
		T[edge[j].first][edge[j].second].push_back({edge[i].first,edge[i].second,st});
	}
	
	int dy[8]={1,1,1,0,0,-1,-1,-1};
	int dx[8]={-1,0,1,-1,1,-1,0,1};
	FOR(y,H) FOR(x,W) {
		FOR(i,8) {
			int ty=y+dy[i];
			int tx=x+dx[i];
			if(ty<0||ty>=H||tx<0||tx>=W) continue;
			int st=(B[ty+1][tx+1]&R[y+1][x+1])|(R[ty+1][tx+1]&B[y+1][x+1]);
			T[y][x].push_back({ty,tx,st});
		}
		sort(ALL(T[y][x]));
		T[y][x].erase(unique(ALL(T[y][x])),T[y][x].end());
	}
	
	ll mi=1<<30;
	ll cnt=0;
	FOR(y,H) FOR(x,W) {
		if(R[y+1][x+1]) {
			pair<ll,ll> ret=hoge(y,x);
			if(ret.first<mi) {
				mi=ret.first;
				cnt=0;
			}
			if(ret.first==mi) cnt+=ret.second;
			cost[y][x]=1<<20;
		}
	}
	
	if(mi>=1<<20) {
		cout<<"No"<<endl;
	}
	else {
		cnt=cnt%mo*(mo+1)/2%mo;
		cout<<"Yes"<<endl;
		cout<<mi<<" "<<cnt%mo<<endl;
	}
	
	
}

まとめ

Editorialでは割愛されてるけど、グリッド周辺部の扱いが一番しんどい。