Codeforces ECR #107 : E. Colorings and Dominoes

後半が難しめの回。
https://codeforces.com/contest/1511/problem/E

問題

白黒で塗られたグリッドが与えられる。
このうち、白いマスをW個とする。
白いマスをそれぞれ赤か青で塗ることを考えると、2^W通りの塗り方が考えられる。

この時、以下のように２マス分の大きさのドミノを置く。

• ドミノを横２マスにわたって置く場合、いずれも赤マスでなければならない。
• ドミノを縦２マスにわたって置く場合、いずれも青マスでなければならない。

2^W通りの塗り方に対し、ドミノを置ける最大数の総和を求めよ。

解法

まず横向きのドミノの数を数えることを考える。
この時、行単位で数を最大化することを考えればよいので、行単位で数え上げを行おう。
他の行における白マス数をVとすると、１行分における色の塗り分け方及びドミノ数に対し、2^Vを掛ければよい。

同様に、縦向きのドミノの数も列単位で数えればよい。

int H,W;
int TW;
string S[303030];
const ll mo=998244353;
ll p2[303030];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	p2[0]=1;
	FOR(i,301010) p2[i+1]=p2[i]*2%mo;
	
	
	cin>>H>>W;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) if(S[y][x]=='o') TW++;
	}
	ll ret=0;
	FOR(y,H) {
		ll p[2]={1,0};
		int lef=TW;
		FOR(x,W) {
			if(S[y][x]=='*') {
				p[0]=(p[0]+p[1])%mo;
				p[1]=0;
			}
			else {
				ll t[2]={0,0};
				lef--;
				// blue
				t[1]+=p[0];
				t[0]+=p[1];
				(ret+=p[1]*p2[lef])%=mo;
				//red
				t[0]+=p[0]+p[1];
				
				p[0]=t[0]%mo;
				p[1]=t[1]%mo;
			}
		}
	}
	FOR(x,W) {
		ll p[2]={1,0};
		int lef=TW;
		FOR(y,H) {
			if(S[y][x]=='*') {
				p[0]=(p[0]+p[1])%mo;
				p[1]=0;
			}
			else {
				ll t[2]={0,0};
				lef--;
				// blue
				t[1]+=p[0];
				t[0]+=p[1];
				(ret+=p[1]*p2[lef])%=mo;
				//red
				t[0]+=p[0]+p[1];
				
				p[0]=t[0]%mo;
				p[1]=t[1]%mo;
			}
		}
	}
	cout<<ret<<endl;
	
	
}

まとめ

こっちはそこまで難しくないかな。