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

2025年2月8日
情報オリンピック日本委員会

問題文

JOI 学園の理恵さんは，今年 3 月に実施される文化祭のポスターを作った． このポスターは N 行 N 列のマス目の形をしており，各マスは 1 から K までの番号が付けられた K 種類の色のいずれかで塗られている． 具体的には，ポスターの上から i 行目，左から j 列目 (1 ≦ i ≦ N，1 ≦ j ≦ N) は色 A_i,j で塗られている．

しかし，このポスターについて生徒間で話し合いを行ったところ，もう少しカラフルにした方が良いのではないかという意見が出た． 具体的には，以下で定義されるカラフル度を上げた方が良いのではないかという意見が出た．

• 連続する 2 行 2 列の正方形領域のうち，3 種類以上の色を含むものの個数．

たとえば，下図左のようなポスターを作った場合，下図右に示す 2 つの長方形領域について 3 種類以上の色を含むため，カラフル度は 2 である．

ポスターの提出期限まであと数分しかないので，以下の操作を 0 回または 1 回行うことで，カラフル度を最大化したい．

• 好きなマスを 1 つ選び，そのマスの色を K 種類の色のいずれかで塗り替える．

理恵さんが最初に作ったポスターの情報が与えられるので，達成できるカラフル度の最大値を求めるプログラムを作成せよ．

制約

• 2 ≦ N ≦ 270．
• 3 ≦ K ≦ 10⁹．
• 1 ≦ A_i,j ≦ K (1 ≦ i ≦ N，1 ≦ j ≦ N)．
• 入力される値はすべて整数である．

小課題

1. (9 点) N = 2，K = 3．
2. (6 点) A_i,j (1 ≦ i ≦ N，1 ≦ j ≦ N) はすべて異なる．
3. (27 点) N ≦ 10，K ≦ 10．
4. (26 点) N ≦ 10．
5. (32 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N K
A_1,1 A_1,2 … A_1,N
A_2,1 A_2,2 … A_2,N
︙
A_N,1 A_N,2 … A_N,N

出力

達成できるカラフル度の最大値を 1 行で出力せよ．

入出力例

入力例 1
2 3
1 2
2 1

出力例 1
1

以下のように，上から 2 行目，左から 2 列目のマスを色 3 で塗り替えることで，カラフル度 1 を達成することができる．

カラフル度 2 以上を達成する方法はないため，1 を出力する．

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

入力例 2
5 5
1 1 1 2 2
1 1 1 2 2
3 3 1 2 2
3 3 5 5 5
3 3 5 5 5

出力例 2
5

以下のように，上から 2 行目，左から 3 列目のマスを色 4 で塗り替えることで，カラフル度 5 を達成することができる．

カラフル度 6 以上を達成する方法はないため，5 を出力する．

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

入力例 3
5 1000000000
104289385 946930886 881692778 914636916 257747795
524238335 819885386 849760493 696516649 389641422
225202363 550490028 883368690 302520060 344897765
267513928 565180541 740383427 404089172 503455737
135005211 621595368 394702567 926956430 436465782

出力例 3
16

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

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

出力例 4
2

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

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

出力例 5
39

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