Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 264 C問題 Matrix Reducing

AtCoder ABC ABC264 C問題 300 pts

問題

提出解答

問題の概要

$H_1$ 行 $W_1$ 列の行列 $A=(A_{i,j})$ と $H_2$ 行 $W_2$ 列の行列 $B=(B_{i,j})$ が与えられる.

次の操作を $0$ 回以上行うことにより, $A$ を $B$ に一致させることができるか?

$A$ から1行選び, その行を削除する.
$A$ から1列選び, その列を削除する.

制約

$1 \leq H_2 \leq H_1 \leq 10$
$1 \leq W_2 \leq W_1 \leq 10$
$1 \leq A_{i,j}, B_{i,j} \leq 10^9$

解法

$A$ のうちのどの $H_2$ 行, どの $W_2$ 行を残すかを決め打つと, 残りの行, 列に対してはどのような順番で削除しても結果は同じである.

このことから, どの $H_2$ 行, どの $W_2$ 行を残すか? ということのみが重要になる. ここで, $A$ にある $H_1$ 行のうち, 行の残し方の場合の数は $2^{H_1}$ 通りである. 列についても $2^{W_1}$ 通りである.

よって, 行, 列の残し方の場合の数は $2^{H_1+W_1}$ 通りであり, 今回は $H_1, W_1 \leq 10$ であり, $2^{20}=1048576$ より各パターンを全て生成しても間に合う.

この各パターンの生成の方法として bit 全探索が用いられる. この bit 全探索を用いることで, 計算量 $O(H_1 W_1 2^{H_1 W_1})$ 時間となる. ここで, 明らかに残す行, 列の数が $H_1, W_1$ 個ではない場合は $B$ に一致させられないということに注意して実装しないと実行時間制限に間に合わないプログラミング言語があるかもしれない.