【競技プログラミング】AtCoder Beginner Contest 267_C問題

問題

要約

1. 2つの行列A(H1行W1列)とB(H2行W2列)が与えられる。
2. 行列Aに対して、以下の2つの操作を任意の回数（0回も含む）行うことができる。
   • Aの任意の1行を削除する
   • Aの任意の1列を削除する
3. これらの操作を行った後、行列AをBと一致させることができるかどうかを判定する。

• H1: 行列Aの行数
• W1: 行列Aの列数
• H2: 行列Bの行数
• W2: 行列Bの列数
• Ai,j: 行列Aのi行j列目の要素
• Bi,j: 行列Bのi行j列目の要素

既存投稿一覧ページへのリンク

一覧ページ

解法手順1

行列Aから行と列を削除して行列Bと一致させることができるかを、全ての可能な削除パターンを試すことで判定する。

1. 入力から行列AとBの情報を読み取る。
2. 行列Aの各行を残すか削除するかの全ての組み合わせを生成する。
3. 行列Aの各列を残すか削除するかの全ての組み合わせを生成する。
4. 2と3で生成した各組み合わせに対して以下の処理を行う
   a. 選択された行と列だけを使って新しい行列を作成する。
   b. 新しい行列のサイズが行列Bと同じかチェックする。
   c. サイズが同じ場合、新しい行列と行列Bの全ての要素を比較する。
5. 全ての要素が一致する組み合わせが見つかった場合、"Yes"を出力して終了する。
6. 全ての組み合わせを試しても一致するものが見つからなかった場合、"No"を出力する。

ACコード1

ac.py

from itertools import product

def io_func():
    # 行列Aの行数と列数を入力
    H1, W1 = map(int, input().split())
    # 行列Aの要素を入力
    A = [list(map(int, input().split())) for _ in range(H1)]
    # 行列Bの行数と列数を入力
    H2, W2 = map(int, input().split())
    # 行列Bの要素を入力
    B = [list(map(int, input().split())) for _ in range(H2)]
    return H1, W1, A, H2, W2, B

def create_new_matrix(A, row_mask, col_mask):
    # 選択された行と列だけを使って新しい行列を作成
    return [[A[i][j] for j in range(len(A[0])) if col_mask[j]] for i in range(len(A)) if row_mask[i]]

def compare_matrices(matrix1, matrix2):
    # 二つの行列が完全に一致するかチェック
    return all(row1 == row2 for row1, row2 in zip(matrix1, matrix2))

def solve(H1, W1, A, H2, W2, B):
    # 行と列の全ての組み合わせを生成
    for row_mask in product([0, 1], repeat=H1):
        for col_mask in product([0, 1], repeat=W1):
            # 新しい行列を作成
            new_matrix = create_new_matrix(A, row_mask, col_mask)
            
            # 新しい行列のサイズが行列Bと同じかチェック
            if len(new_matrix) == H2 and len(new_matrix[0]) == W2:
                # 新しい行列と行列Bを比較
                if compare_matrices(new_matrix, B):
                    return "Yes"
    
    # 一致する組み合わせが見つからなかった場合
    return "No"

# メイン処理
H1, W1, A, H2, W2, B = io_func()
result = solve(H1, W1, A, H2, W2, B)
print(result)

###
# H1, W1: 行列Aの行数と列数
# A: 行列A
# H2, W2: 行列Bの行数と列数
# B: 行列B
# row_mask: 行を残すか削除するかを示すマスク
# col_mask: 列を残すか削除するかを示すマスク
# new_matrix: 選択された行と列から作成された新しい行列

# 1. io_func関数: 標準入力から行列AとBの情報を読み取る
# 2. create_new_matrix関数: 与えられた行と列のマスクに基づいて新しい行列を作成
# 3. compare_matrices関数: 二つの行列が完全に一致するかチェック
# 4. solve関数: 全ての可能な行と列の組み合わせを試し、条件を満たす組み合わせがあるかチェック
# 5. メイン処理: io_func関数で入力を受け取り、solve関数で結果を計算し、結果を出力

オブジェクト指向版1

ac.py

from abc import ABC, abstractmethod
from itertools import product
from typing import List, Tuple

class MatrixReader(ABC):
    @abstractmethod
    def read_matrix(self) -> Tuple[int, int, List[List[int]]]:
        pass

class ConsoleMatrixReader(MatrixReader):
    def read_matrix(self) -> Tuple[int, int, List[List[int]]]:
        # 行列の行数と列数を入力
        H, W = map(int, input().split())
        # 行列の要素を入力
        matrix = [list(map(int, input().split())) for _ in range(H)]
        return H, W, matrix

class MatrixOperations:
    @staticmethod
    def create_new_matrix(matrix: List[List[int]], row_mask: Tuple[int], col_mask: Tuple[int]) -> List[List[int]]:
        # 選択された行と列だけを使って新しい行列を作成
        return [[matrix[i][j] for j in range(len(matrix[0])) if col_mask[j]] for i in range(len(matrix)) if row_mask[i]]

    @staticmethod
    def compare_matrices(matrix1: List[List[int]], matrix2: List[List[int]]) -> bool:
        # 二つの行列が完全に一致するかチェック
        return all(row1 == row2 for row1, row2 in zip(matrix1, matrix2))

class MatrixSolver:
    def __init__(self, matrix_a: List[List[int]], matrix_b: List[List[int]]):
        self.matrix_a = matrix_a
        self.matrix_b = matrix_b

    def solve(self) -> str:
        H1, W1 = len(self.matrix_a), len(self.matrix_a[0])
        H2, W2 = len(self.matrix_b), len(self.matrix_b[0])

        # 行と列の全ての組み合わせを生成
        for row_mask in product([0, 1], repeat=H1):
            for col_mask in product([0, 1], repeat=W1):
                # 新しい行列を作成
                new_matrix = MatrixOperations.create_new_matrix(self.matrix_a, row_mask, col_mask)
                
                # 新しい行列のサイズが行列Bと同じかチェック
                if len(new_matrix) == H2 and len(new_matrix[0]) == W2:
                    # 新しい行列と行列Bを比較
                    if MatrixOperations.compare_matrices(new_matrix, self.matrix_b):
                        return "Yes"
        
        # 一致する組み合わせが見つからなかった場合
        return "No"

# Open/Closed Principle: MatrixReaderは拡張可能だが変更はしない
class MatrixProblemSolver:
    def __init__(self, reader: MatrixReader):
        self.reader = reader

    def solve(self) -> str:
        # 行列Aを読み込む
        _, _, matrix_a = self.reader.read_matrix()
        # 行列Bを読み込む
        _, _, matrix_b = self.reader.read_matrix()

        solver = MatrixSolver(matrix_a, matrix_b)
        return solver.solve()

# メイン処理
if __name__ == "__main__":
    reader = ConsoleMatrixReader()
    problem_solver = MatrixProblemSolver(reader)
    result = problem_solver.solve()
    print(result)

# H, W: 行列の行数と列数
# matrix: 入力された行列
# row_mask: 行を残すか削除するかを示すマスク
# col_mask: 列を残すか削除するかを示すマスク
# new_matrix: 選択された行と列から作成された新しい行列

# 1. MatrixReader: 行列の読み込みを抽象化
# 2. ConsoleMatrixReader: コンソールからの行列入力を実装
# 3. MatrixOperations: 行列操作のユーティリティメソッドを提供
# 4. MatrixSolver: 行列の比較ロジックを実装
# 5. MatrixProblemSolver: 問題全体の解決を管理