結果

問題 No.3060 Erase Binary Matrix
コンテスト
ユーザー tute7627
提出日時 2025-01-26 01:35:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,955 bytes
コンパイル時間 344 ms
コンパイル使用メモリ 82,332 KB
実行使用メモリ 86,744 KB
最終ジャッジ日時 2025-03-12 00:39:06
合計ジャッジ時間 7,812 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 8 WA * 5 TLE * 1 -- * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve():
    import sys
    input_data = sys.stdin.read().strip().split()
    if not input_data:
        return
    H = int(input_data[0])
    W = int(input_data[1])
    matrix = []
    idx = 2
    for _ in range(H):
        s = input_data[idx]
        idx += 1
        # 各行は01文字列なので、各文字をintに変換してリストにする
        row = list(map(int, s))
        matrix.append(row)
    
    # 操作1・2による「自由削除」を行う関数
    def free_deletion(mat):
        changed = True
        while changed:
            changed = False
            # 操作１: 各行が定数ならその行を削除
            new_mat = []
            for row in mat:
                if row and all(x == row[0] for x in row):
                    changed = True
                    continue  # この行は削除
                new_mat.append(row)
            mat = new_mat
            
            if not mat:  # 行がなくなった場合終了
                break

            # 操作２: 各列が定数ならその列を削除
            if mat and (len(mat[0]) > 0):
                ncols = len(mat[0])
                cols_to_del = []
                for j in range(ncols):
                    col = [row[j] for row in mat]
                    if len(set(col)) == 1:  # j列が定数なら
                        cols_to_del.append(j)
                if cols_to_del:
                    new_mat = []
                    for row in mat:
                        new_row = [val for j, val in enumerate(row) if j not in cols_to_del]
                        new_mat.append(new_row)
                    mat = new_mat
                    changed = True
        return mat

    # 初めに自由削除を実施
    matrix = free_deletion(matrix)
    
    op3_count = 0  # 操作３（任意削除）の回数

    # 行列が空（または列がなくなる）まで処理を続ける
    while matrix and matrix[0]:
        num_rows = len(matrix)
        num_cols = len(matrix[0])
        best_row = 0
        best_score = -1
        
        # 各行を削除候補として評価
        for r in range(num_rows):
            new_mat = matrix[:r] + matrix[r+1:]
            score = 0
            # new_matが空ならすべて削除につながるとみなす
            if not new_mat:
                score = num_cols
            else:
                for j in range(num_cols):
                    col = [row[j] for row in new_mat]
                    if len(set(col)) == 1:
                        score += 1
            if score > best_score:
                best_score = score
                best_row = r
        
        # 貪欲に選んだ行を操作３で削除
        matrix.pop(best_row)
        op3_count += 1
        
        # 再度自由削除フェーズを適用
        matrix = free_deletion(matrix)
    
    sys.stdout.write(str(op3_count) + "\n")

if __name__ == '__main__':
    solve()
0