結果
| 問題 |
No.1954 CHECKER×CHECKER(2)
|
| ユーザー |
 lam6er
|
| 提出日時 | 2025-03-20 20:20:27 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 68 ms / 1,000 ms |
| コード長 | 6,369 bytes |
| コンパイル時間 | 150 ms |
| コンパイル使用メモリ | 82,348 KB |
| 実行使用メモリ | 72,432 KB |
| 最終ジャッジ日時 | 2025-03-20 20:21:17 |
| 合計ジャッジ時間 | 2,530 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 29 |
ソースコード
def main():
import sys
input = sys.stdin.read().split()
idx = 0
H = int(input[idx]); idx +=1
W = int(input[idx]); idx +=1
S = []
for _ in range(H):
s = input[idx].strip(); idx +=1
row = [1 if c == '#' else 0 for c in s]
S.append(row)
M = int(input[idx]); idx +=1
type1 = [] # list of n_i for type1 operations
type2 = [] # list of n_i for type2 operations
seen1 = set()
seen2 = set()
for _ in range(M):
t = int(input[idx]); idx +=1
n = int(input[idx]); idx +=1
if t == 1:
if n not in seen1:
type1.append(n)
seen1.add(n)
else:
if n not in seen2:
type2.append(n)
seen2.add(n)
type1 = sorted(type1)
type2 = sorted(type2)
def check_pattern(target_generator):
# Generate c matrix
c = [[0]* (W+1) for _ in range(H+1)] # 1-based
for i in range(1, H+1):
for j in range(1, W+1):
target = target_generator(i, j)
s_val = S[i-1][j-1]
c[i][j] = target ^ s_val
# Check row consistency
base_row = 1
row_diff = [0]*(H+1)
for i in range(1, H+1):
row_diff[i] = c[i][1] ^ c[base_row][1]
for j in range(1, W+1):
expected = c[base_row][j] ^ row_diff[i]
if c[i][j] != expected:
return None
# Check column consistency
base_col = 1
col_diff = [0]*(W+1)
for j in range(1, W+1):
col_diff[j] = c[base_row][j] ^ c[base_row][base_col]
for i in range(1, H+1):
expected = c[i][base_col] ^ col_diff[j]
if c[i][j] != expected:
return None
# Construct two possible solutions
solutions = []
# Solution 1: rows1[1] =0
rows1 = [0]*(H+1)
cols1 = [0]*(W+1)
for i in range(1, H+1):
rows1[i] = row_diff[i]
for j in range(1, W+1):
cols1[j] = c[base_row][j]
solutions.append((rows1, cols1))
# Solution 2: rows2[1] =1
rows2 = [0]*(H+1)
cols2 = [0]*(W+1)
for i in range(1, H+1):
rows2[i] = row_diff[i] ^ 1 # row_diff[i] is c[i][1]^c[1][1], so rows[1] =1→1^0 → row_diff[i]^1
for j in range(1, W+1):
cols2[j] = c[base_row][j] ^1
solutions.append((rows2, cols2))
return solutions
# Check two possible checkerboard patterns
# Pattern 1: (i+j) %2 ==0
def target1(i, j):
return (i + j) % 2
solutions1 = check_pattern(target1)
# Pattern 2: (i+j+1) %2 ==0
def target2(i, j):
return (i + j +1) %2
solutions2 = check_pattern(target2)
# Now, check if any solution can be formed by the operations
def can_form(target, type_list, max_dim):
# target is a list [1..max_dim], 1-based.
# type_list is list of n_i operations.
# max_dim is H or W.
# Check if the target can be represented as the XOR of some operations in type_list.
# Operations are (1-based)n_i: prefix.
# Gauss elimination for binary vectors (mod 2)
basis = {}
# Sort operations in decreasing order
sorted_ops = sorted(type_list, reverse=True)
for n in sorted_ops:
vec = [0]*(max_dim +1)
for r in range(1, n+1):
vec[r] = 1
# Reduce this vector
current = vec.copy()
pivot = -1
for r in range(max_dim, 0, -1):
if current[r] ==1:
pivot = r
break
if pivot == -1:
continue # zero vector, skip
if pivot not in basis:
basis[pivot] = current
else:
# XOR with basis[pivot]
for r in range(1, pivot+1):
current[r] ^= basis[pivot][r]
# Find new pivot
new_pivot = -1
for r in range(pivot-1, 0, -1):
if current[r] ==1:
new_pivot = r
break
if new_pivot == -1:
continue # no new pivot
else:
# Check if this new_pivot is in basis
while new_pivot in basis:
# XOR with basis[new_pivot]
for r in range(1, new_pivot+1):
current[r] ^= basis[new_pivot][r]
# Find next pivot
new_pivot = -1
for r in range(new_pivot-1, 0, -1):
if current[r] ==1:
new_pivot = r
break
if new_pivot == -1:
break
if new_pivot != -1:
basis[new_pivot] = current.copy()
# Now, check if target can be formed
current = [0]*(max_dim+1)
for r in range(1, max_dim+1):
current[r] = target[r]
# Apply basis vectors in reverse order
for pivot in sorted(basis.keys(), reverse=True):
if current[pivot]:
# XOR with basis[pivot]
for r in range(1, pivot+1):
current[r] ^= basis[pivot][r]
# Check if all zero
return sum(current[1:max_dim+1]) ==0
found = False
for solutions in [solutions1, solutions2]:
if not solutions:
continue
for rows, cols in solutions:
# Check rows via type1 operations
target_rows = [0]*(H+1)
for r in range(1, H+1):
target_rows[r] = rows[r]
ok_rows = can_form(target_rows, type1, H)
if not ok_rows:
continue
# Check cols via type2 operations
target_cols = [0]*(W+1)
for c in range(1, W+1):
target_cols[c] = cols[c]
ok_cols = can_form(target_cols, type2, W)
if ok_cols:
found = True
break
if found:
break
print("Yes" if found else "No")
if __name__ == "__main__":
main()