Bで躓いていまいちだった回。
https://codeforces.com/contest/1239/problem/A
問題
H*Wのグリッドを白黒に塗り分ける。
その際、各セルの、隣接セルに、同色のセルが最大1個となるケースは何通りか。
解法
一番上の行を左から埋めることを考える。
同じ色は3つ連続できないため、直前2個のセルの色を持ってDPしていけばよい。
もし同じ色の2つ連続が1か所でもある場合、以降の行は上の行と同じでなければならないので、各行の色は確定する。
行と列を入れ替えても同様。
ただし、完全に市松模様のケースは両方で二重カウントしてしまうので、そこだけ引いておこう。
int H,W; const ll mo=1000000007; ll dp[101010][2][2]; void solve() { int i,j,k,l,r,x,y; string s; cin>>H>>W; ll ret=0; FOR(i,2) { ZERO(dp); if(W==1) { ret+=2; } else { dp[2][0][1]=1; dp[2][1][0]=1; dp[2][0][0]=1; dp[2][1][1]=1; for(j=3;j<=W;j++) { dp[j][0][0]=dp[j-1][1][0]; dp[j][1][1]=dp[j-1][0][1]; dp[j][0][1]=(dp[j-1][1][0]+dp[j-1][0][0])%mo; dp[j][1][0]=(dp[j-1][0][1]+dp[j-1][1][1])%mo; } ret+=dp[W][0][0]+dp[W][0][1]+dp[W][1][0]+dp[W][1][1]; } swap(W,H); } ret+=mo-2; cout<<ret%mo<<endl; }
まとめ
ここまではよかったんだけどね。