No.452 横着者のビンゴゲーム

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 51
作問者 : matsu7874matsu7874

1 ProblemId : 1455 / 出題時の順位表

注意書き

Python3は想定解でTLEしました。

ビンゴゲームの説明

ビンゴゲームをご存知だろうか。

各プレイヤーにはNマス×Nマスのビンゴカードを1枚ずつ配られる。
各マスには自然数が書かれている。

司会者はカゴの中にそれらの数が書かれた球をいれ、ランダムに球を取り出し、
取り出した球にかかれている数を読み上げる。
司会者が読み上げる数が自分のカードにあればそのマスを消す。
縦・横・対角線のいずれかが揃う、つまりNマス連続してマスが消えた状態になれば「ビンゴ」となり景品がもらえるというゲームである。

通常ビンゴゲームの司会者は一つずつ球を取り出し、一つずつ読み上げ、その都度、ビンゴになった参加者がいないか確認を行う。

※1枚のカードの中に同じ自然数が繰り返し登場することはない。

ストーリー

横着者のビンゴゲームの司会者がいた。
彼は今、M人のプレイヤーの中から1人だけ優勝者(最も早くビンゴになったプレイヤー)を決めたいと考えている。

彼は横着なので、複数人が同時にビンゴにならないことが保証できる限りできるだけ多くの球をまとめて取り出す。
つまり通常の司会者は数を一つずつ抽選し、読み上げるのに対し、彼はいくつかまとめて球を取り出し、まとめて読み上げる。
いくつかの球をまとめて読み上げた後で、まとめて読み上げたグループを参加者に処理させ、ビンゴになったプレイヤーの存在を確認する。

ただ1つだけ球を取り出したとしても、複数人が同時にビンゴになる可能性が排除できないときは
「同時にビンゴになったらじゃんけんで決めて」と断った上で1つだけ球を取り出すことにしている。

さて、これからビンゴゲームを始めるが、一番初めに球を取り出す時、彼はいくつの球を取り出すだろうか。

問題文

Nマス×NマスのビンゴカードM枚の情報が与えられる。
X個の球をまとめて取り出し、それぞれの球に対応する数を消した時、
ビンゴになっているカードの枚数が1枚超える可能性のない最大の整数Xを求めよ。

入力

N M
C111 C112 ... C11N
C121 C122 ... C12N
...
C1N1 C1N2 ... C1NN
...
CM11 CM12 ... CM1N
CM21 CM22 ... CM2N
...
CMN1 CMN2 ... CMNN

一行目にはビンゴカードの大きさを表すNとプレイヤーの人数を表すMが半角スペース区切りで与えられる。
続くN×M行にはN行ずつプレイヤーごとのカードの情報が与えられる。
例えば、2行目からのN行にはプレイヤー1のカード情報であり、続くN行はプレイヤー2のカードの情報である。
ビンゴカードの情報のそれぞれの行にはN個のマスにかかれている自然数が与えられる。

  • $ 2 \le N \le 100 $
  • $ 2 \le M \le 200 $
  • ただし$ NM \le 400 $を満たす。
  • $ 1 \le C_{kij} \le N^2M $
  • 1枚のカードの中に同じ自然数が繰り返し登場することはない。

出力

X個の球をまとめて取り出し、それぞれの球に対応する数を消した時、
ビンゴになっているカードの枚数が1枚超える可能性のない最大の整数Xを出力せよ。
最後に改行せよ。

サンプル

サンプル1
入力
2 2
1 2
3 4
5 6
7 8
出力
3

球を4つ選ぶと2人がビンゴになってしまう可能性があります。
例:{1,2,5,6}でプレイヤー1が1-2でビンゴ、プレイヤー2が5-6でビンゴとなります。
一方で3つまでであればどのように選んでも2人以上がビンゴになることはありません。
従って答えは3になります。

サンプル2
入力
3 2
1 2 3
4 5 6
7 8 9
1 10 3
12 13 14
15 8 6
出力
3

サンプル3
入力
3 4
28 14 15
18 16 25
30 29 4
21 7 2
28 1 10
16 5 12
4 12 10
17 2 5
6 35 18
15 24 9
16 25 29
14 22 10
出力
3

提出ページヘ