TopCoder SRM 655 Div2: Easy

16回目のSRM。EasyMed提出でEasy通過、161位。1080 → 1097 (+17)。

問題はこちらから

問題

一辺50マス以下の正方形のボードが与えられる。ボードの各マスは白か黒か"？"である。各"？"には白か黒の好きな方の色を塗れるとしたとき、隣接するマスが同じ色にならないようにボードを塗ることができるかどうか答えよ。

解答

奇数マス、偶数マスでの各色の数を数えていけばいい。隣接するマスが同じ色にならないように塗れるのは、"？"マスを除いて、偶数マスには白のみで奇数マスには黒のみ、または偶数マスには黒のみで奇 数マスには白のみ、のどちらかのときのみ。この条件さえ満たせばあとは与えられた条件を満たすように"？"マスを塗ることができる。本番ではシミュレーションをしたが、こちらの方が早くて簡潔に書ける。

def ableToDraw(self, board):
    H,W = len(board),len(board[0])
    odd_W = odd_B = even_W = even_B = 0
    for y in xrange(H):
        for x in xrange(W):
            if board[y][x] == "B":
                if (y+x)%2 == 0:
                    even_B += 1
                else:
                    odd_B += 1
            if board[y][x] == "W":
                if (y+x)%2 == 0:
                    even_W += 1
                else:
                    odd_W += 1
    return "Possible" if (odd_W == even_B == 0 or even_W == odd_B == 0) else "Impossible"