遅れて参加したこともあり微妙な出来。
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; }
まとめ
問題を誤読して手間取った。