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}

vec_r[i] には、$i$ 行目にコマがある列番号を記録する。
vec_c[i] には、$i$ 列目にコマがある行番号を記録する。
コマがない場合は、-1 を記録する。

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

vec_r: {-1, -1, -1, -1}
vec_c: {-1, -1, -1, -1}

$1$ 回目の操作は $(1,1)$ である。
$1$ 行目と $1$ 列目にはコマがないので、そのままマス $(1,1)$ にコマを置く。

vec_r: {-1, 1, -1, -1}
vec_c: {-1, 1, -1, -1}

$2$ 回目の操作は $(1,2)$ である。
vec_r[1]=1 なので、$1$ 行目にあるマス $(1,1)$ のコマを削除する。
そのため、vec_c[1] と vec_r[1] を -1 にする。

$2$ 列目にはコマがない。
その後、マス $(1,2)$ にコマを置く。

vec_r: {-1, 2, -1, -1}
vec_c: {-1, -1, 1, -1}

$3$ 回目の操作は $(3,3)$ である。
$3$ 行目と $3$ 列目にはコマがないので、そのままマス $(3,3)$ にコマを置く。

vec_r: {-1, 2, -1, 3}
vec_c: {-1, -1, 1, 3}

$4$ 回目の操作は $(3,2)$ である。
vec_r[3]=3 なので、$3$ 行目にあるマス $(3,3)$ のコマを削除する。
そのため、vec_c[3] と vec_r[3] を -1 にする。

次に、vec_c[2]=1 なので、$2$ 列目にあるマス $(1,2)$ のコマを削除する。
そのため、vec_r[1] と vec_c[2] を -1 にする。

その後、マス $(3,2)$ にコマを置く。

vec_r: {-1, -1, -1, 2}
vec_c: {-1, -1, 3, -1}

$5$ 回目の操作は $(1,3)$ である。
$1$ 行目と $3$ 列目にはコマがないので、そのままマス $(1,3)$ にコマを置く。

vec_r: {-1, 3, -1, 2}
vec_c: {-1, -1, 3, 1}

$6$ 回目の操作は $(1,3)$ である。
vec_r[1]=3 なので、$1$ 行目にあるマス $(1,3)$ のコマを削除する。
そのため、vec_c[3] と vec_r[1] を -1 にする。

この時点で vec_c[3]=-1 なので、$3$ 列目から削除するコマはない。
最後に、マス $(1,3)$ にコマを置き直す。

vec_r: {-1, 3, -1, 2}
vec_c: {-1, -1, 3, 1}

最後に、vec_r のうち、-1 でない要素の個数を数える。

result: 2

特になし。

特になし。