問題一覧 > 通常問題

No.1908 Assault for Keys

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 115
作問者 : chineristACchineristAC / テスター : Kanten4205Kanten4205 tokusakuraitokusakurai
5 ProblemId : 6935 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-05 23:07:48

問題文

chinerist 君はインデント幅を1にしてコーディングしていた罪で yuki 刑務所に投獄されてしまいました。

yuki 刑務所には $N$ 人の看守 $i\ (1\le i \le N)$ がいて、各看守は $M$ 種類の鍵 $j\ (1\le j \le M)$ のうちいくつかを所持しています。 看守 $i$ が各鍵を所持しているかについては o,x のみからなる長さ $M$ の文字列 $S_i=S_{i1}S_{i2}\dots S_{iM}$ で表され、 $S_{ij}=$o のとき看守 $i$ が鍵 $j$ を所持していることを、$S_{ij}=$x のとき看守 $i$ が鍵 $j$ を所持していないことを表します。 各鍵 $j\ (1\le j \le M)$ は $1$ 人以上の看守が所持しています。

yuki 刑務所から脱獄するには $M$ 種類の鍵がそれぞれ $1$ つ以上必要です。 chinerist 君は何人かの看守を襲って、それぞれが所持している鍵をすべて強奪することで鍵を集めることにしました。

以下の条件を満たす最小の整数 $K$ を求めてください。

条件
  • $N$ 人の看守のうちどの $K$ 人を襲っても、$M$ 種類の鍵をそれぞれ $1$ つ以上手に入れることができる

入力

$N$ $M$
$S_1$
$S_2$
$\vdots$
$S_N$
  • $1 \le N \le 1000$
  • $1 \le M \le 1000$
  • $S_i$ はox のみからなる長さ $M$ の文字列
  • 各 $j\ (1\le j \le M)$ に対し、 $S_{ij}=$o を満たす $i$ が1つ以上存在する

出力

答えを出力してください。

最後に改行してください。

サンプル

サンプル1
入力
3 3
oxo
xoo
oox
出力
2

看守 $1$ だけ襲うと鍵 $2$ が集められません。

看守 $1,\ 2$ を襲うと $3$ 種類の鍵はすべて集まります。

看守を $2$ 人襲う方法として他に看守 $2,\ 3$ を襲う、看守 $1,\ 3$ を襲う、の $2$ 通りありますが、いずれの方法でも $3$ 種類の鍵はすべて集まります。

よって条件を満たす最小の $K$ は $2$ です。

サンプル2
入力
10 15
ooxxxxooooxoxox
ooxxxooxooxxxxx
ooooooxooooxxxx
oxxoxooxoxoooxx
oxooooxoooooxoo
ooooxoxooooxxox
oxooxoxoooxxxxx
ooxoxoxoooooxoo
oooxoooxooxooxo
oxoxxoxooooxoxx
出力
8

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。