結果

問題 No.1974 2x2 Flipper
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:09:59
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 5,106 bytes
コンパイル時間 216 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 94,080 KB
最終ジャッジ日時 2025-05-14 13:11:15
合計ジャッジ時間 6,354 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 21 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Function to read input and solve the problem
def solve():
    # Read dimensions H (height/rows) and W (width/columns) from input
    H, W = map(int, sys.stdin.readline().split())

    # Handle the edge case where the grid is too small for any operations.
    # If H=1 or W=1, no 2x2 square exists, so no operations can be performed.
    # The grid remains all white. The maximum number of black cells is 0.
    if H == 1 or W == 1:
        print(0)
        # Print the grid state (all 0s)
        for _ in range(H):
            # Create a list of W zeros and print them space-separated
            print(*( ([0] * W) ))
        return

    # We will use 0-based indexing internally for list indices in Python.
    # The grid A has dimensions H x W, with indices (0..H-1, 0..W-1).
    # Operations are defined by their top-left corner (i, j).
    # The possible indices for operations are 0 <= i <= H-2 and 0 <= j <= W-2.
    # We use a matrix X of size (H-1) x (W-1) to store whether each operation is performed.
    # X[i][j] = 1 if the operation starting at (i, j) is performed, 0 otherwise.
    
    # Initialize the X matrix with all zeros.
    X = [[0] * (W - 1) for _ in range(H - 1)]

    # Calculate the values for the X matrix using a greedy strategy.
    # The strategy is to determine the operations X[i][j] such that all cells
    # A[k][l] in the top-left (H-1) x (W-1) subgrid become black (1).
    # We iterate through the possible operation indices (i, j) which correspond
    # to the cell indices (k, l) in the target subgrid A[0..H-2][0..W-2].
    for r in range(H - 1): # row index `r` for X, corresponds to grid row `k=r`
        for c in range(W - 1): # column index `c` for X, corresponds to grid column `l=c`
            
            # The final state of cell A[r][c] is determined by the sum modulo 2 of operations
            # that affect it. These are operations based at (r,c), (r-1,c), (r,c-1), (r-1,c-1).
            # A[r][c] = (X[r][c] + X[r-1][c] + X[r][c-1] + X[r-1][c-1]) % 2
            # (Indices out of bounds for X contribute 0).
            # We want to set A[r][c] = 1.
            
            # When we are determining X[r][c], the values X[r-1][c], X[r][c-1], and X[r-1][c-1]
            # have already been determined by processing previous rows/columns.
            # Let S be the sum modulo 2 of contributions from these known X values.
            S = 0
            # Contribution from X[r-1][c] (operation above)
            if r > 0:
                S ^= X[r-1][c] # XOR is equivalent to sum modulo 2 for binary values
            # Contribution from X[r][c-1] (operation to the left)
            if c > 0:
                S ^= X[r][c-1]
            # Contribution from X[r-1][c-1] (operation diagonally top-left)
            if r > 0 and c > 0:
                 S ^= X[r-1][c-1] 
            
            # The target state is A[r][c] = 1.
            # The current equation is: A[r][c] = (X[r][c] + S) % 2
            # We need (X[r][c] + S) % 2 = 1.
            # This means X[r][c] must be 1 if S is 0, and 0 if S is 1.
            # In other words, X[r][c] = 1 - S (mod 2).
            # This is equivalent to X[r][c] = 1 ^ S in binary arithmetic.
            X[r][c] = 1 ^ S

    # After determining all X[i][j] values, calculate the final state of the grid A.
    A = [[0] * W for _ in range(H)]
    total_black_cells = 0

    # Iterate through all cells (r, c) of the grid A.
    for r in range(H): # Grid row index k = r
        for c in range(W): # Grid column index l = c
            
            # Calculate the final state A[r][c].
            # It's the sum modulo 2 of X[i][j] for operations (i,j) that affect cell (r,c).
            # The operations affecting cell (r,c) are those based at
            # (r, c), (r-1, c), (r, c-1), (r-1, c-1).
            # We only sum X[i][j] if the index (i, j) is valid for an operation:
            # 0 <= i <= H-2 and 0 <= j <= W-2.
            
            val = 0 # Accumulates the sum modulo 2
            
            # Check contribution from X[r][c]
            if 0 <= r <= H - 2 and 0 <= c <= W - 2:
                 val ^= X[r][c]

            # Check contribution from X[r-1][c]
            if 0 <= r - 1 <= H - 2 and 0 <= c <= W - 2:
                 val ^= X[r-1][c]

            # Check contribution from X[r][c-1]
            if 0 <= r <= H - 2 and 0 <= c - 1 <= W - 2:
                 val ^= X[r][c-1]
                 
            # Check contribution from X[r-1][c-1]
            if 0 <= r - 1 <= H - 2 and 0 <= c - 1 <= W - 2:
                 val ^= X[r-1][c-1]
            
            # Set the final state of cell A[r][c]
            A[r][c] = val
            # Count the cell if it's black (1)
            if val == 1:
                total_black_cells += 1

    # Output the maximum number of black cells found
    print(total_black_cells)
    # Output the grid configuration that achieves this maximum
    for r in range(H):
        # Print each row with elements separated by spaces
        print(*(A[r]))

# Call the solve function to run the program
solve()
0