日本情報オリンピック第1回女性部門　問題6

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

2021年4月27日
情報オリンピック日本委員会

問題６	デジタルアート (Digital Art)　(配点 100点) 　　時間制限 : 1 sec / メモリ制限 : 1024 MB

問題文

JOI 高校の生徒である葵はデジタルアート制作が趣味であり，今日も新しい画像を作った．

この画像のサイズは，縦 H ピクセル，横 W ピクセルであり，H × W のマス目のような形で表される．ここで，上から i 行目 (1 ≦ i ≦ H)，左から j 列目 (1 ≦ j ≦ W) のピクセルを (i, j) で表す．各ピクセルは 1 つの色で塗られている．各色には 1 から 256 までの番号が付けられており，ピクセル (i, j) の色の番号は A_{i, j} である．

葵はこの画像を同級生である凛に見せたが，凛は「画像に使われている色の種類が多すぎる」という理由で気に入らなかった．そこで葵は，以下のように画像内のある領域を隠して，見える色の種類をできるだけ少なくできないかと考えた．

葵は S 個以下のピクセルを選んで隠す．
ただし，隠すピクセルの領域は 1 つの長方形で表されなければならない．

画像のデータと，隠すピクセルの個数の上限 S が与えられたとき，画像内のある領域を隠したときに見える色の種類の数としてありうる最小の値を求めるプログラムを作成せよ．

制約

1 ≦ H ≦ 1 000．
1 ≦ W ≦ 1 000．
1 ≦ S ≦ HW．
1 ≦ A_{i, j} ≦ 256 (1 ≦ i ≦ H，1 ≦ j ≦ W)．
入力される値はすべて整数である．

小課題

(8 点) H = 1，W ≦ 10．
(10 点) H ≦ 10，W ≦ 10．
(5 点) S = 1．
(6 点) A_{i, j} ≦ 2 (1 ≦ i ≦ H，1 ≦ j ≦ W)．
(5 点) A_{i, j} ≦ 4 (1 ≦ i ≦ H，1 ≦ j ≦ W)．
(13 点) A_{i, j} ≦ 15 (1 ≦ i ≦ H，1 ≦ j ≦ W)．
(13 点) A_{i, j} ≦ 30 (1 ≦ i ≦ H，1 ≦ j ≦ W)．
(15 点) A_{i, j} ≦ 70 (1 ≦ i ≦ H，1 ≦ j ≦ W)．
(25 点) 追加の制約はない．

採点に関する注意

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解となる．

各提出の得点は，提出されたソースコードが正解した小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

入力

入力は以下の形式で標準入力から与えられる．
H W S
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}

出力

標準出力に，画像内のある領域を隠したときに見える色の種類の数としてありうる最小の値を 1 行で出力せよ．

特に，見えるピクセルが一つもない状態にできる場合は 0 と出力せよ．

入出力例

入力例 1
1 10 7
5 1 2 5 2 2 5 6 6 5

出力例 1
2

例えば，左から数えて 2 番目から 8 番目までのピクセルを隠すと，番号 5, 6 の色だけが見え，その種類の数は 2 となる．この場合，隠すピクセルは 7 個となり，条件を満たす．また，葵は見える色を 1 種類以下にすることはできない．よって 2 を出力する．

この入力例は小課題 1, 2, 6, 7, 8, 9 の制約を満たす．

入力例 2
10 10 45
1 1 1 1 1 1 1 1 1 1
1 1 1 2 2 3 3 1 1 1
1 1 2 1 2 3 1 3 1 1
1 2 1 2 6 6 3 1 3 1
1 2 2 6 1 1 6 3 3 1
1 4 4 6 1 1 6 5 5 1
1 4 1 4 6 6 5 1 5 1
1 1 4 1 4 5 1 5 1 1
1 1 1 4 4 5 5 1 1 1
1 1 1 1 1 1 1 1 1 1

出力例 2
4

例えば，左上をピクセル (2, 1)，右下をピクセル (7, 7) とする長方形領域を隠すと，番号 1, 3, 4, 5 の色だけが見え，その種類の数は 4 となる．この場合，隠すピクセルは 42 個となり，条件を満たす．

この説明を図で表すと，以下のようになる．

この入力例は小課題 2, 6, 7, 8, 9 の制約を満たす．

入力例 3
5 10 1
2 3 5 7 1 1 1 3 1 7
1 9 2 3 2 9 3 1 3 7
4 1 4 3 4 7 5 3 5 9
6 1 6 7 7 1 7 3 7 9
8 3 8 9 9 7 2 3 5 7

出力例 3
9

隠すピクセルを S = 1 個以下にするという条件の下では，葵は番号 1, 2, 3, ..., 9 の 9 種類の色が見えるようにしかできない．よって 9 を出力する．

この入力例は小課題 2, 3, 6, 7, 8, 9 の制約を満たす．

入力例 4
9 6 54
1 1 1 1 1 3
6 14 14 3 3 12
9 13 1 10 3 3
9 13 5 5 3 3
6 13 10 3 7 3
2 5 8 5 3 3
6 5 5 3 15 3
6 5 10 5 3 3
2 2 5 7 3 3

出力例 4
0

54 個すべてのピクセルを隠して，見えるピクセルが一つもないようにできる．よって 0 を出力する．

この入力例は小課題 2, 6, 7, 8, 9 の制約を満たす．

入力例 5
8 10 59
3 3 3 3 3 3 3 3 2 3
3 1 3 3 3 3 3 2 3 3
3 3 1 4 3 4 2 3 3 3
3 3 3 1 4 2 4 3 3 3
3 3 3 4 1 4 2 3 3 3
3 3 3 1 4 3 4 2 3 3
3 3 1 3 3 3 3 3 2 3
3 1 3 3 3 3 3 3 3 3

出力例 5
2

例えば，左上をピクセル (3, 1)，右下をピクセル (10, 7) とする長方形領域を隠すと，番号 1, 3 の色だけが見え，その種類の数は 2 となる．この場合，隠すピクセルは 56 個となり，条件を満たす．

この説明を図で表すと，以下のようになる．

この入力例は小課題 2, 5, 6, 7, 8, 9 の制約を満たす．