SRM 553 500pt : TwoConvexShapes
問題概要
W*H(<50)のボードがあり、各マスは白か黒か?になっている。今、?に色を付けてconvexになるようにしたい。そのような方法が何通りあるか求める問題。ボードがconvexであるとは、各列、行を見たとき全部白か全部黒か白->黒か黒->白になっているものをいう。
解法
除原理で重複を排除する。
左が白で右が黒で白の個数が行番号について単調非減少であるようなものは簡単にできて、同様のものが4つ計算できる。その部分は簡単なDP。
で、重複を排除する。全部白や全部黒や、縦に分割線があるものや横に分割線があるものは重複しているので適当に差っ引く。
こういう問題は、方針は見えやすいのだけど場合分けを減らして事故が起こらないようにしなければならない(あまり惜しいとか意味の無い問題)。どうやってシンプルな形に落とし込めるのかはまだよく分かっていない。
acceptされたコード
DPの部分は累積和などで計算量をもっと落とせる。
#include <vector> #include <algorithm> #include <cstring> #include <string> using namespace std; const int MAX_W = 50; typedef long long int64; const int64 MOD = (int64)( 1e9 + 7 ); struct TwoConvexShapes { int countWays(vector <string> grid) { int64 ans = 0; int H = grid.size(), W = grid[0].length(); for (int _ = 0; _ < 2; ++_) { for (int __ = 0; __ < 2; ++__) { ans += solve(grid); for (int i = 0; i < H; ++i) { reverse(grid[i].begin(), grid[i].end()); } } for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { grid[i][j] = (grid[i][j] == 'W' ? 'B' : grid[i][j] == 'B' ? 'W' : '?'); } } } for (int _ = 0; _ < 2; ++_) { for (int mid = 1; mid < W; ++mid) { bool leftB = true, rightB = true; bool leftW = true, rightW = true; for (int i = 0; i < H; ++i) { for (int j = 0; j < mid; ++j) if (grid[i][j] != '?') { leftB &= grid[i][j] == 'B'; leftW &= grid[i][j] == 'W'; } for (int j = mid; j < W; ++j) if (grid[i][j] != '?') { rightB &= grid[i][j] == 'B'; rightW &= grid[i][j] == 'W'; } } if (leftB && rightW) { ans = (ans - 1 + MOD) % MOD; } if (leftW && rightB) { ans = (ans - 1 + MOD) % MOD; } } { vector<string> tmp(W, string(H, '.')); for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { tmp[j][i] = grid[i][j]; } } grid = tmp; swap(H, W); } } bool canAllB = true, canAllW = true; for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) if (grid[i][j] != '?') { canAllB &= grid[i][j] != 'W'; canAllW &= grid[i][j] != 'B'; } } if (canAllB) { ans = (ans - 3 + MOD) % MOD; } if (canAllW) { ans = (ans - 3 + MOD) % MOD; } return int(ans % MOD); } int64 solve(vector<string> board) { const int H = board.size(), W = board[0].length(); static int64 ways[MAX_W + 1][MAX_W + 1]; memset(ways, 0, sizeof(ways)); ways[0][0] = 1; for (int i = 0; i < H; ++i) { for (int j = 0; j <= W; ++j) { bool ok = true; for (int k = 0; k < j; ++k) { ok &= board[i][k] == '?' || board[i][k] == 'B'; } for (int k = j; k < W; ++k) { ok &= board[i][k] == '?' || board[i][k] == 'W'; } if (ok) { for (int k = 0; k <= j; ++k) { ways[i+1][j] = (ways[i+1][j] + ways[i][k]) % MOD; } } } } int64 ans = 0; for (int i = 0; i <= W; ++i) { ans = (ans + ways[H][i]) % MOD; } return ans; } };