yukicoder No.226 0-1パズル
いやぁこれ結構実装大変だと思うんですけど…
なんか一発ACしてる人多いですねぇ。
解法
基本的な方針は,「上の行が決まると下の行も決まるんじゃね?」ということです。
この予想はある程度正しくて,上の行に少なくともひとつ0か1が連続している部分があると,下の行は完全に一意に決定します(上の行をbit反転したものが下の行)。
ただ,上の行が01010101...のように1つおきにバラバラだと下の行は101010101...のようにbit反転するものと,01010101...のように上と同じbit行にするものの2通りがあります。
実装の方針は,
すべての行を0101010のように1つおきにバラバラにするものと,1行目を適当に決めたらそれより下の行が決定されるもの,に場合分けする,という方針でやりました(若干場合がかぶるのでなんとかする)。
1つおきにバラバラの場合は1行ずつ見ていって0からスタートするものと1からスタートするものが存在するかを見ていきます。
1行目を決めて残り全部を決める場合は,すべて反転していないと行けないので例えば下のように0,1が決まっていたとすると,
?11?
???0
次のように0,1が決定します。
?111
?000
1行目の残りの?は好きに決めて良いので2とおりです。
後は気合でACしました。
const int MAX = 111; const ll MOD = 1e9+7; int H, W; string board[MAX]; ll calc() { for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (board[i][j] != '?') { for (int k = 0; k < H; k++) { const int diff = abs(i-k) % 2; int should = board[i][j] - '0'; if (diff == 1) should ^= 1; char c = (char)('0'+should); if (board[k][j] != '?' && board[k][j] != c) { return 0; } board[k][j] = c; } } } } //for (int i = 0; i < H; i++) cout << board[i] << endl; ll ans = 1; for (int i = 0; i < W; i++) { if (board[0][i] == '?') (ans *= 2) %= MOD; } return ans; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> H >> W; for (int i = 0; i < H; i++) cin >> board[i]; ll ans = 1; for (int i = 0; i < H; i++) { // 101010的something int ok = 0; // 最初1, 最初0 でないと11 for (int j = 0; j < W; j++) { if (board[i][j] == '0') { if (j%2) ok |= 2; else ok |= 1; } if (board[i][j] == '1') { if (j%2) ok |= 1; else ok |= 2; } } int tmp = 2-__builtin_popcount(ok); ans *= tmp; ans %= MOD; } ll tmp = calc(); ans += tmp; ll cnt = 0; if (tmp != 0) { int ok = 0; // 最初1, 最初0 でないと11 for (int i = 0; i < W; i++) { if (board[0][i] == '0') { if (i%2) ok |= 2; else ok |= 1; } if (board[0][i] == '1') { if (i%2) ok |= 1; else ok |= 2; } cnt = 2-__builtin_popcount(ok); } } cout << (ans-cnt) % MOD << endl; return 0; }