HHKB プログラミングコンテスト 2020 : E - Lamps

Eまで順調だったがFで詰まった。
https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_e

問題

H*Wのグリッドがあり、一部のマスは埋まっている。
空きマスのいくつかにランプを置いたとする。
ランプは、埋まったマスにぶつかるまで上下左右方向の空きマスをすべて照らす。

2^(空きマス)だけランプを置くマスの選び方は考えられるが、それぞれ照らされたマスの数の総和を求めよ。

解法

各マスが何通りのパターンで照らされるかを考える。
上下左右に累積和を取り、各マスを照らしうるランプのマスの数を数えよう。
そのようなマスがn個あり、全空きマスがm個あるなら、(m-n)個のランプの有無はどうでもよく、n個中1個が置かれていればよいので、2^m*(2^n-1)を掛け合わせよう。

int H,W;
string S[2020];
const ll mo=1000000007;
ll p2[2020*2020];
int U[2020][2020];
int D[2020][2020];
int L[2020][2020];
int R[2020][2020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,2020*2010) p2[i+1]=p2[i]*2%mo;
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	
	int sum=0;
	FOR(y,H) {
		FOR(x,W) if(S[y][x]=='.') {
			sum++;
			if(x&&S[y][x-1]=='.') L[y][x]=L[y][x-1]+1;
		}
		for(x=W-1;x>=0;x--) if(S[y][x]=='.') {
			if(x+1<W&&S[y][x+1]=='.') R[y][x]=R[y][x+1]+1;
		}
	}
	FOR(x,W) {
		FOR(y,H) if(S[y][x]=='.') {
			if(y&&S[y-1][x]=='.') U[y][x]=U[y-1][x]+1;
		}
		for(y=H-1;y>=0;y--) if(S[y][x]=='.') {
			if(y+1<H&&S[y+1][x]=='.') D[y][x]=D[y+1][x]+1;
		}
	}
	
	ll ret=0;
	FOR(y,H) FOR(x,W) if(S[y][x]=='.') {
		int tot=1+L[y][x]+R[y][x]+U[y][x]+D[y][x];
		(ret+=p2[sum-tot]*(p2[tot]-1)%mo)%=mo;
		
	}
	cout<<ret%mo<<endl;
}

まとめ

これは割と典型なので、サクサク行けた。