ABC466 D - Placing Rooks

ルーク配置

考え方

コマの置き方のルールにより、各行・各列最大 $1$ つしかコマを置けない。
よって、各行「何列目にコマがあるか、またはどこにもないか」でコマ配置は十分表せる。

しかしこれでは問題がある。
これでは、ある列のコマを削除するのに、全ての行を見なければならない。
そこで、各列「何行目にコマがあるか、またはどこにもないか」も重ねて情報を持つことにする。

ここまで来れば、あとは問題通りにシミュレーションするだけである。
つまり、$1$ つの操作ごとに以下を処理すればよい。

$1$ 回の処理が $O(1)$ なので、事前処理も含めて全体の計算量は $O(N+M)$。

入力を受け取る。

n: 3
m: 6
r: {1, 1, 3, 3, 1, 1}
c: {1, 2, 3, 2, 3, 3}

最初は、どのマスにもコマがない。

各操作で削除されるコマと、操作後に残るコマは次のようになる。

操作	行側で削除	列側で削除	操作後のコマ
$(1,1)$	なし	なし	$\{(1,1)\}$
$(1,2)$	$(1,1)$	なし	$\{(1,2)\}$
$(3,3)$	なし	なし	$\{(1,2),(3,3)\}$
$(3,2)$	$(3,3)$	$(1,2)$	$\{(3,2)\}$
$(1,3)$	なし	なし	$\{(1,3),(3,2)\}$
$(1,3)$	$(1,3)$	なし	$\{(1,3),(3,2)\}$

$4$ 回目の操作では、まず $3$ 行目から $(3,3)$ を削除する。
その後、$2$ 列目から $(1,2)$ を削除してから $(3,2)$ を置く。

$6$ 回目の操作では、$1$ 行目の $(1,3)$ を一度削除する。
この時点で $3$ 列目にはコマがないので、列側では何も削除せず、最後に $(1,3)$ を置き直す。

最終的に残るコマは $(1,3)$ と $(3,2)$ の $2$ 個なので、答えは $2$ となる。

特になし。

特になし。