http://codeforces.com/contest/1027/problem/E
N*Nの盤面を白と黒で塗る。
以下の条件を満たす塗り方をmod998244353で答えよ。
- 隣接する横の列の塗り方が全く同じか逆である
- 隣接する横の行の塗り方が全く同じか逆である
- 面積がK以上の長方形が1つの色だけで塗られていることが無い
前提知識
考察過程
1. mod数え上げなので、とりあえずdpを考えてみる
2. N≦500なのでN^3のDPっぽい
3. 条件をもうちょっと噛み砕いて考えてみる
4. 全く同じか逆であることが列と行で言われているが、どちらか満たせば、どちらも満たす
5. 重要な方針「一列確定すればDPできそう」
6. 1列確定していれば、同色の連続する最大サイズと同じ塗り方を何回されているかを記憶しておけば、1つの色だけで塗られている長方形の最大面積がわかる
7. DP[x][ma][last] := x列目まで確定していて、列の同色の連続する最大サイズがmaで、最後尾で同じ塗り方がlast回されているときの組合せ
8. これは手応えがある
9. あとは、1列目の塗り方について調べる必要があるが、これもDPできる
10. DP[y][ma][last] := y行目まで確定していて、同色の連続する最大サイズがmaで、最後尾で同色がlast回連続しているときの組合せ
11. 計算量的にも難易度的にもそれっぽい解法ができた
解法
http://codeforces.com/contest/1027/submission/41807084
2回DPをして計算をしよう。
まずは1列目の塗り方を計算する。
dp1[y][ma][last] := y行目まで確定していて、同色の連続する最大サイズがmaで、最後尾で同色がlast回連続しているときの組合せ
最後が黒か白かというのは保存してもよいが、どちらにしろ遷移は変わらないので、同一視して問題ない。
dp1[y + 1][max(ma, last + 1)][last + 1] += dp1[y][ma][last];
最後尾の色で塗る遷移
dp1[y + 1][ma][1] += dp1[y][ma][last];
最後尾と逆の色で塗る遷移
次に1列目で横に塗っていったときの全体の組合せを計算する。
dp2[x][ma][last] := x列目まで確定していて、列の同色の連続する最大サイズがmaで、最後尾で同じ塗り方がlast回されているときの組合せ
if (ma * (last + 1) < K) dp2[x + 1][ma][last + 1] += dp2[x][ma][last];
最後尾の列を同じ塗り方で塗る。
if (ma < K) dp2[x + 1][ma][1] += dp2[x][ma][last];
最後尾の列と逆の塗り方で塗る。
以下を実装する。
するとMLE。
int N, K; mint dp1[505][505][505]; mint dp2[505][505][505]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> K; dp1[1][1][1] = 2; rep(y, 1, N) rep(ma, 1, N + 1) rep(last, 1, N + 1) { dp1[y + 1][max(ma, last + 1)][last + 1] += dp1[y][ma][last]; dp1[y + 1][ma][1] += dp1[y][ma][last]; } rep(ma, 1, N + 1) rep(last, 1, N + 1) if(ma < K) dp2[1][ma][1] += dp1[N][ma][last]; rep(x, 1, N) rep(ma, 1, N + 1) rep(last, 1, N + 1) { if (ma * (last + 1) < K) dp2[x + 1][ma][last + 1] += dp2[x][ma][last]; if (ma < K) dp2[x + 1][ma][1] += dp2[x][ma][last]; } mint ans = 0; rep(ma, 1, N + 1) rep(last, 1, N + 1) ans += dp2[N][ma][last]; cout << ans << endl; }
x,yの部分を節約すると通る。
int N, K; mint dp1[2][505][505]; mint dp2[2][505][505]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> K; dp1[1][1][1] = 2; rep(_y, 1, N) { int y = _y % 2; int yy = 1 - y; rep(ma, 1, N + 1) rep(last, 1, N + 1) dp1[yy][ma][last] = 0; rep(ma, 1, N + 1) rep(last, 1, N + 1) { dp1[yy][max(ma, last + 1)][last + 1] += dp1[y][ma][last]; dp1[yy][ma][1] += dp1[y][ma][last]; } } rep(ma, 1, N + 1) rep(last, 1, N + 1) if(ma < K) dp2[1][ma][1] += dp1[N % 2][ma][last]; rep(_x, 1, N) { int x = _x % 2; int xx = 1 - x; rep(ma, 1, N + 1) rep(last, 1, N + 1) dp2[xx][ma][last] = 0; rep(ma, 1, N + 1) rep(last, 1, N + 1) { if (ma * (last + 1) < K) dp2[xx][ma][last + 1] += dp2[x][ma][last]; if (ma < K) dp2[xx][ma][1] += dp2[x][ma][last]; } } mint ans = 0; rep(ma, 1, N + 1) rep(last, 1, N + 1) ans += dp2[N % 2][ma][last]; cout << ans << endl; }
