AtCoder Beginner Contest 264 F問題 Monochromatic Path

$H$ 行 $W$ 列からなるマス目がある. 上から $i$ 行目, 左から $j$ 列目のマス (以降ではマス $(i,j)$ と呼ぶことにする) は $A_{i,j}=0$ ならば白, $A_{i,j}=1$ ならば黒である.

以下の操作から1つ選び, 実行することを $0$ 回以上行うことができる.

このとき, 次の目標を達成するためにかかる合計費用の最小値を求めよ.

マス $(1,1)$ から「現在いるマスの右隣もしくは下隣のマスに移動する」を繰り返してマス $(H,W)$ に到達する経路のうち, 全てのマス (両端含む) の色が同じであるようなものが存在する.

以降ではマスの色を $\mathbb{Z}/2 \mathbb{Z}$ で表すことにする.

次のような問題に切り替える.

次の操作を行い, マス $(H,W)$ に到達したときにおける最小費用を求めよ.

以下の2つの操作を行うか行わないかを選び, 行うことを選んだ場合は実行する.
- $R_1$ 円払い, $1$ 行目のマスの白黒を全て反転させる.
- $C_1$ 円払い, $1$ 列目のマスの白黒を全て反転させる.
マス $(1,1)$ に降り立つ.
次の操作をマスに到達するまで行う.
- 以下の2つの操作で可能な操作のうち, 1つを選び実行する (今いるマスをマス $(i,j)$ とする).

動的計画法で解くことにする. ${\rm DP}[i,j,r,c]$ を以下で設定する.

マス $(i,j)$ に到達し, $i$ 列目の白黒を反転してい ( $r=0$ : ない, $r=1$ る), $j$ 列目の白黒を反転してい ( $c=0$ : ない, $c=1$ る) 状態における最小費用

ここで, ${\rm DP}$ の各要素は全て $+\infty$ で初期化し, ${\rm DP}[i,j,r,c] \gets \alpha$ については ${\rm DP}[i,j,r,c] \gets \min({\rm DP}[i,j,r,c], \alpha)$ を省略した表記とする.

ベースケースは $i=j=1$ のときであり, このときは降り立つ前に色の反転を行うことから,

である.

更新式について考える. $(i,j,r,c)$ のとき, マス $(i,j)$ の色は $A_{i,j} \oplus r \oplus c$ *1である.

下に移動するとき ( $i \lt H$ ), マス $(i+1,j)$ の色は $A_{i,j} \oplus c$ である. よって,

$A_{i,j} \oplus r \oplus c=A_{i+1,j} \oplus c$ ならば ${\rm DP}[i+1,j,0,c] \gets {\rm DP}[i,j,r,c]$ .
$A_{i,j} \oplus r \oplus c \neq A_{i+1,j} \oplus c$ ならば ${\rm DP}[i+1,j,1,c] \gets {\rm DP}[i,j,r,c]+R_{i+1}$ .

となる.

右に移動するとき ( $j \lt W$ ) も同様にして,

$A_{i,j} \oplus r \oplus c=A_{i,j+1} \oplus r$ ならば ${\rm DP}[i,j+1,r,0] \gets {\rm DP}[i,j,r,c]$ .
$A_{i,j} \oplus r \oplus c \neq A_{i,j+1} \oplus r$ ならば ${\rm DP}[i,j+1,r,1] \gets {\rm DP}[i,j,r,c]+C_{j+1}$ .