日本情報オリンピック 第3回 女性部門

2023年1月24日
情報オリンピック日本委員会

問題文

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

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

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

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

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

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

制約

• H ≧ 1．
• W ≧ 2．
• H × W ≦ 500 000．
• 1 ≦ A_i,j ≦ 10⁹ (1 ≦ i ≦ H，1 ≦ j ≦ W)．
• 入力される値はすべて整数である．

小課題

1. (6 点) H = 1．
2. (20 点) H ≦ 2．
3. (27 点) H ≦ 200，W ≦ 200．
4. (47 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
H W
A_1,1 A_1,2 … A_1,W
A_2,1 A_2,2 … A_2,W
:
A_H,1 A_H,2 … A_H,W

出力

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

入出力例

入力例 1
4 4
1 1 1 3
2 2 1 3
2 1 1 3
2 2 2 2

出力例 1
4

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 の制約を満たす．

入力例 2
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

出力例 2
8

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

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

入力例 3
1 6
1 1 2 2 3 3

出力例 3
3

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

入力例 4
2 10
1 1 1 1 1 3 3 3 3 4
1 2 1 3 3 3 1 1 3 3

出力例 4
6

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