Kazun の競プロ記録

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

AtCoder Beginner Contest 283 E問題 Don't Isolate Elements

AtCoder ABC283 ABC E問題 500 pts

問題

提出解答

問題の概要

各要素が $0$ または $1$ であるような $H$ 行 $W$ 列の行列 $A$ が与えられる.

$1 \leq i \leq H, 1 \leq j \leq W$ に対して, 以下を満たすような整数の組 $(x,y)$ が存在しないとき, $(i,j)$ 要素は孤立した要素であるという.

$(x,y)$ は $(i-1,j), (i+1,j), (i,j-1), (i,j+1)$ のいずれかである.
$1 \leq x \leq H, 1 \leq y \leq W$
$A_{i,j}=A_{x,y}$

次の操作を $0$ 回行うことで, $A$ に孤立した要素が存在しないようにすることは可能か? 可能ならばその操作回数の最小値を求めよ.

$1 \leq i \leq H$ である整数 $i$ を選ぶ. その後, $1 \leq j \leq W$ である全ての整数 $j$ に対して, $A_{i,j} \gets 1-A_{i,j}$ とする.

制約

$2 \leq H,W \leq 1000$
$A_{i,j} \in \{0,1\}$

解法

同じ $i$ に対して2回以上操作すると最小性に反するので, 各 $i$ に対する操作は $1$ 回までとすることができる.

$i=1,2, \dots, H$ の順に操作をする/しないを確定させていくとする. $i$ 行目に対する操作の有無が決定すると, $(i-1)$ 行目の各要素が孤立するかどうかが確定する. また, $(i-1)$ 行目の孤立性においては $(i-2), (i-1), i$ 行目以外は関与しない.

このことから, $i$ 行目に関して見るとき, $(i-2), (i-1)$ 行目を操作したかということについて場合分けすれば良さそうである.

次のような動的計画法を考える. ただし, $i \geq 2, s,t \in \{0,1\}$ とする.

${\rm DP}[i,s,t$ ] : $i$ 行目まで見たとき, $(i-1)$ 行目を操作 ( $s$ : する/ しない), $i$ 行目を操作 ( $s$ : する/ しない) ような場合における操作回数の最小値 (存在しない場合は $+\infty$ )

今回のベースケースは $i=2$ のときである. $(s,t)$ に対応する操作を行った後, $1$ 行目に孤立した要素が存在するならば, ${\rm DP}[2,s,t]=+\infty$ , 存在しないのならば ${\rm DP}[2,s,t ]=s+t$ である.

更新式について, 各 $t,u \in \{0,1\}$ に対して, $s \in \{0,1\}$ のうち, $(i-2), (i-1), i$ 行目に $s,t,u$ に対応する操作を行った後, $(i-1)$ 行目に孤立した要素が存在しないような組からなる集合を $E_{i,t,u}$ と置くことにすると

$\displaystyle {\rm DP}[i,t,u]=\min_{s \in E_{i,t,u}} \left({\rm DP}[i,s,t]+u \right)$

である. $i=H$ まで完了すると, $H$ 行目まで確定させて, $(H-1)$ 行目まで孤立した要素が存在しないことが確定しているので, 最後に $H$ 行目に孤立した要素が存在しないかどうかを確認する必要がある.

組 $(t,u)$ のうち, $(t,u)$ に対応する操作を行った後, $H$ 行目に孤立した要素が存在しないような組の集合を $F$ とおく. このとき, 答えは

$\displaystyle \min_{(t,u) \in F} {\rm DP}[H, t, u]$

である. 計算量は $O(HW)$ 時間である.