kmjp's blog

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

Codeforces ECR #049 : E. Inverse Coloring

遅れて参加したこともあり微妙な出来。
http://codeforces.com/contest/1027/problem/E

問題

N*Nのグリッドを白黒に塗り分ける。
その際、隣接する列同士または行同士は、まったく同じ塗り方か、白黒正反対に塗らなければならない。
この時、面積がK以上の同色の矩形が存在しない塗り分け方は何通りか。

解法

まず1行分のN列の塗り方のうち、同じ色が最長何マス続く箇所があるかをDPで求めよう。
これは直前何マス色が一致するかと、全体で最長何マス色が一致するかを状態で持つとO(N^3)で解ける。

1行において最長pマス同色が連続一致する場合、ceil(K/p)行同じ色を繰り返すと条件に反してしまう。
各pに対し、直前何行同色が続いたかを状態に持ってDPすれば、O(N^3)で同じ色の繰り返しがceil(K/p)行未満であるケースを数え上げることができる。

ll mo=998244353;
int N,K;

ll from[501][501];
ll to[501][501];
ll F[501];
ll T[501];
ll pat[501];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>K;
	from[0][0]=1;
	FOR(i,N) {
		ZERO(to);
		FOR(x,N) FOR(y,N) {
			// same
			to[max(x,y+1)][y+1]+=from[x][y];
			if(to[max(x,y+1)][y+1]>=mo) to[max(x,y+1)][y+1]-=mo;
			// other
			to[max(x,1)][1]+=from[x][y];
			if(to[max(x,1)][1]>=mo) to[max(x,1)][1]-=mo;
		}
		
		swap(from,to);
	}
	
	ll ret=0;
	for(i=1;i<=N;i++) {
		FOR(x,N+1) pat[i]+=from[i][x];
		pat[i]%=mo;
		
		ZERO(F);
		if(i<K) F[1]=1;
		FOR(j,N-1) {
			ZERO(T);
			FOR(x,N+1) {
				if(x*i>=K) break;
				// same
				if((x+1)*i<K) {
					T[x+1]+=F[x];
					if(T[x+1]>=mo) T[x+1]-=mo;
				}
				if(i<K) {
					T[1]+=F[x];
					if(T[1]>=mo) T[1]-=mo;
				}
			}
			swap(F,T);
		}
		
		ll tot=0;
		FOR(x,N+1) tot+=F[x];
		(ret+=pat[i]*(tot%mo))%=mo;
		
	}
	
	
	cout<<ret%mo<<endl;
}

まとめ

問題を誤読して手間取った。