E - 運河 (Canal)

Contest Duration: 2023-01-22(Sun) 04:00 - 2023-01-22(Sun) 08:00 (local time) (240 minutes) Back to Home

E - 運河 (Canal) Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点： $100$ 点

問題文

JOIG 王国は $H$ 行 $W$ 列のマス目に区切られた長方形の形をしている．上から $i$ 行目 ( $1 \leqq i \leqq H$ )，左から $j$ 列目 ( $1 \leqq j \leqq W$ ) のマスをマス $(i,j)$ と呼ぶ．

各マスには標高と呼ばれる整数が定まっている．マス $(i,j)$ の標高は $A_{i,j}$ である．

JOIG 王国では，王国を縦断する運河を建設することにした．運河の建設は，以下のように行われる．

ある整数 $k$ ( $1 \leqq k < W$ ) を定める．左から $k$ 列目と $k+1$ 列目の間に，王国の上端から下端まで縦断する運河を建設する．

運河を横切らず，辺で接している標高が同じマスへの移動を繰り返すことで相互に移動できるマスの集まりをここでは平地と呼ぶ．国土を管理しやすくするため，平地の個数ができるだけ少なくなるように運河の建設位置を決めたい．

JOIG 王国の地形の情報が与えられたとき，運河を建設した後の JOIG 王国内の平地の個数としてありうる最小値を求めるプログラムを作成せよ．

制約

$H \geqq 1$ ．
$W \geqq 2$ ．
$H \times W \leqq 500\,000$ ．
$1 \leqq A_{i,j} \leqq 10^9$ ( $1 \leqq i \leqq H$ ， $1 \leqq j \leqq W$ )．
入力される値はすべて整数である．

小課題

( $6$ 点) $H = 1$ ．
( $20$ 点) $H \leqq 2$ ．
( $27$ 点) $H \leqq 200$ ， $W \leqq 200$ ．
( $47$ 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．

 $H$   $W$ 
 $A_{1,1}$   $A_{1,2}$   $\cdots$   $A_{1,W}$ 
 $A_{2,1}$   $A_{2,2}$   $\cdots$   $A_{2,W}$ 
 $\vdots$ 
 $A_{H,1}$   $A_{H,2}$   $\cdots$   $A_{H,W}$

出力

運河を建設した後の JOIG 王国内の平地の個数としてありうる最小値を出力せよ．

入力例 1Copy

Copy

出力例 1Copy

Copy

$k=3$ として運河を建設すると，JOIG 王国は以下のように $4$ 個の平地に分かれる．

マス $(1,1)$ ， $(1,2)$ ， $(1,3)$ ， $(2,3)$ ， $(3,2)$ ， $(3,3)$ からなる平地
マス $(2,1)$ ， $(2,2)$ ， $(3,1)$ ， $(4,1)$ ， $(4,2)$ ， $(4,3)$ からなる平地
マス $(1,4)$ ， $(2,4)$ ， $(3,4)$ からなる平地
マス $(4,4)$ からなる平地

JOIG 王国内の平地の個数を $3$ 個以下にすることはできないので， $4$ を出力する．

この入力は小課題 $3, 4$ の制約を満たす．

入力例 2Copy

Copy

5 8
1 2 2 5 5 5 5 5
1 1 2 2 5 6 5 6
1 1 1 1 6 6 5 6
1 1 3 1 1 6 7 6
1 4 1 1 1 6 6 6

出力例 2Copy

Copy

$k=1$ として運河を建設すると，JOIG 王国は $8$ 個の平地に分かれる．JOIG 王国内の平地の個数を $7$ 個以下にすることはできないので， $8$ を出力する．

この入力は小課題 $3, 4$ の制約を満たす．

入力例 3Copy

Copy

1 6
1 1 2 2 3 3

出力例 3Copy

Copy

この入力はすべての小課題の制約を満たす．

入力例 4Copy

Copy

2 10
1 1 1 1 1 3 3 3 3 4
1 2 1 3 3 3 1 1 3 3

出力例 4Copy

Copy

この入力は小課題 $2, 3, 4$ の制約を満たす．