yukicoder : No.611 Day of the Mountain

これは本番思いつかなかった。
https://yukicoder.me/problems/no/611

問題

H*Wのグリッドがあり、各マス1～9の値が設定されている。
ただし一部のマスは"?"となっている。

このグリッドを、左上角から右下角まで、隣接する右または下のマスへの移動の繰り返しで到達することを考える。
その際、経由したセルの数値の和がコストだとする。

各セルの"?"に1～9のいずれかを設定したとき、総コストの最小値と、その総コストを達成できる"?"の値の埋め方の組み合わせを求めよ。

解法

コストの最小値は"?"に1を全部埋めれば、ダイクストラなりDPなりで求まる。
まずはこれで左上から各マスに到達する最小コストを求めよう。

次に"?"の埋め方を考える。
H*W＜303より、HとWの少なくとも片方は17以下である。
よってBitDPでどうにかしよう。以下Wが17以下とする。そうでない場合は対角線で反転すればよい。

１行ごとに、各マスに到達した時点で最小コストか否か、を状態として対応する組み合わせ数を求めていこう。
ある行に関し、各マスが最小コストかどうかがわかっている場合、次の行に関し、各マスに最小コストで到達できるかどうかとその組み合わせ数がわかる。
ただ、これを行ごとに行おうとするとO(H*4^W)かかりTLEする。

そこで直前の１行の状態を保持しつつ、１マスずつ状態を更新することにしよう。
今r行c列目の状態を決める場合、直前の状態としてr行目の(1～(c-1))列目と、(r-1)行目の(c～W)列目の計Wマスが最小コストで到達可能かどうかの状態を持ち状態を更新していく。

int H,W;
char S[1010][1010];
int A[1010];
ll mo=201712111;

int mi[2020];
int from[1<<18];
int to[1<<18];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	if(S[0][0]=='?') S[0][0]='1';
	if(S[H-1][W-1]=='?') S[H-1][W-1]='1';
	
	if(H<W) {
		FOR(y,max(H,W)) FOR(x,y) swap(S[y][x],S[x][y]);
		swap(H,W);
	}
	
	FOR(y,H) {
		FOR(x,W) {
			if(S[y][x]=='?') A[y*W+x]=1;
			else A[y*W+x]=S[y][x]-'0';
		}
	}
	
	FOR(x,2020) mi[x]=1<<30;
	mi[0]=A[0];
	FOR(y,H) FOR(x,W) {
		int id=y*W+x;
		if(y) mi[id]=min(mi[id],mi[id-W]+A[id]);
		if(x) mi[id]=min(mi[id],mi[id-1]+A[id]);
	}
	
	from[1]=1;
	int bmask=(1<<W)-1,mask;
	FOR(i,H*W-1) {
		ZERO(to);
		FOR(mask,1<<W) {
			int down=(mask>>(W-1)) && (mi[i-W+1]+A[i+1]==mi[i+1]);
			int right=(mask&1) && (i%W!=W-1) && (mi[i]+A[i+1]==mi[i+1]);
			
			if(down|right) {
				(to[(mask*2+1)&bmask] += from[mask])%=mo;
				(to[(mask*2)&bmask]+=from[mask]*((S[(i+1)/W][(i+1)%W]=='?'?8:0)))%=mo;
			}
			else {
				(to[(mask*2)&bmask]+=from[mask]*(1+(S[(i+1)/W][(i+1)%W]=='?'?8:0)))%=mo;
			}
			
		}
		swap(from,to);
	}
	
	ll ret=0;
	for(mask=1;mask<1<<W;mask+=2) ret+=from[mask];
	cout<<mi[H*W-1]<<endl;
	cout<<ret%mo<<endl;
	
}

まとめ

このグリッド上で右か下しか進めない場合、一見O(H*4^W)に見えてO(HW*2^W)位に落とし込むテク、過去も何度か忘れていたのでいい加減忘れないようにしたい。