No.3311 フィルター
タグ : / 解いたユーザー数 26
作問者 : 👑
p-adic
/ テスター :
yu23578
問題文
数字 $0$ と $1$ のみからなる文字列をbit列と呼びます。
入力に $2$ 個の正整数 $N, M$ と、長さ $N$ のbit列のみからなる要素数 $M$ の集合 $S$ が与えられます。
長さ $N$ のbit列同士のbit積を $\textrm{AND}$ と書き表します。$S$ が良いbit列集合であるとは、以下の $3$ 条件を全て満たすということです：
- 数字 $0$ のみからなる長さ $N$ の文字列は $S$ の要素でない。
- 長さ $N$ の任意のbit列 $s_0$ と $S$ の任意の要素 $s_1$ に対し、$s_0 \textrm{ AND } s_1 = s_1$ ならば $s_0$ は $S$ の要素である。
- $S$ の任意の要素 $s_0$ と $s_1$ に対し、$s_0 \textrm{ AND } s_1$ は $S$ の要素である。
$S$ が良いbit列集合であるか否かを判定してください。
背景
$N$ 以下の正整数全体の集合を $I_N$ と置きます。各 $s \in S$ に対し、条件「$s$ の右から $i$ 文字目が $1$ である」を満たす $i \in I_N$ 全体の集合を $U_s$ と置きます。集合族 $\{U_s \mid s \in S\}$ を $\mathcal{F}_S$ と置くことで、$S$ を $I_N$ の部分集合の集合族 $\mathcal{F}_S$ に翻訳することが出来ます。
集合論や位相空間論、そして順序集合論や束論などではしばしばフィルターという概念が使われます。$S$ が良いbit列集合であるという性質は $\mathcal{F}_S$ が $I_N$ のフィルターであることと同値であるため、この問題は実質 $\mathcal{F}_S$ が $I_N$ のフィルターであるか否かを判定する問題となります。
入力
$S$ の要素を $M$ 以下の各正整数 $m$ で番号付けて $s_m$ と置きます。
この時、入力は次の形式で標準入力から $1 + M$ 行で与えられます：
- $1$ 行目に $N, M$ が半角空白区切りで与えられます。
- $M$ 以下の各正整数 $m$ に対し、$1 + m$ 行目に $s_m$ が与えられます。
$N$ $M$ $s_1$ $\vdots$ $s_M$
制約
入力は以下の制約を満たします：
- $N$ は $1 \leq N \leq 20$ を満たす整数である。
- $M$ は $1 \leq M \leq \min \{2^N,10^5\}$ を満たす整数である。
- $M$ 以下の任意の正整数 $m$ に対し、$s_m$ は長さ $N$ のbit列である。
- $M$ 以下の任意の正整数 $m_0, m_1$ に対し、$m_0 \neq m_1$ ならば $s_{m_0} \neq s_{m_1}$ である。
出力
$S$ が良いbit列集合である場合はYesと出力し、そうでない場合はNoと出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 1 0
出力
No
$S = \{0\}$ であり、特に数字 $0$ のみからなる長さ $N = 1$ の文字列 $0$ が $S$ の要素です。従って条件1に反し、$S$ は良いbit列集合ではありません。
サンプル2
入力
1 1 1
出力
Yes
$S = \{1\}$ であり、
- 数字 $0$ のみからなる長さ $N = 1$ の文字列 $0$ は $S$ の要素でない。
- 長さ $N = 1$ の任意のbit列 $s_0$ と $S$ の任意の要素 $s_1$ に対し、$s_1 = 1$ であるので $s_0 \textrm{ AND } s_1 = s_0$ であり、従って $s_0 \textrm{ AND } s_1 = s_1$ ならば $s_0 = 1$ となり、これは $S$ の要素である。
- $S$ の任意の要素 $s_0$ と $s_1$ に対し、$s_0 = s_1 = 1$ であるので $s_0 \textrm{ AND } s_1 = 1$ となり、これは $S$ の要素である。
より $S$ は良いbit列集合です。
サンプル3
入力
2 1 10
出力
No
$S = \{10\}$ であり、$(s_0,s_1) = (11,10)$ と置くと $s_0$ は長さ $N = 2$ のbit列であり $s_1$ は $S$ の要素です。更に $s_0 \textrm{ AND } s_1 = s_1$ が成り立ちますが、$s_0$ は $S$ の要素ではありません。従って条件2に反し、$S$ は良いbit列集合ではありません。
サンプル4
入力
2 1 11
出力
Yes
$S = \{11\}$ であり、
- 数字 $0$ のみからなる長さ $N = 2$ の文字列 $00$ は $S$ の要素でない。
- $s_0$ を長さ $N = 2$ のbit列とし、$s_1$ を $S$ の要素とする。この時 $s_1 = 11$ であるので $s_0 \textrm{ AND } s_1 = s_0$ であり、従って $s_0 \textrm{ AND } s_1 = s_1$ ならば $s_0 = 11$ となり、これは $S$ の要素である。
- $s_0$ と $s_1$ を $S$ の要素とする。この時 $s_0 = s_1 = 11$ であるので $s_0 \textrm{ AND } s_1 = 11$ となり、これは $S$ の要素である。
より $S$ は良いbit列集合です。
サンプル5
入力
2 2 01 11
出力
Yes
$S = \{01,11\}$ であり、
- 数字 $0$ のみからなる長さ $N = 2$ の文字列 $00$ は $S$ の要素でない。
- $s_0$ を長さ $N = 2$ のbit列とし、$s_1$ を $S$ の要素とする。この時 $s_1$ は $01$ か $11$ のいずれかである。$s_0 \textrm{ AND } s_1 = s_1$ ならば、$s_1 = 01$ の場合 $s_0$ は $01$ か $11$ のいずれかであり $s_1 = 11$ の場合 $s_0$ は $11$ である。従っていずれの場合も $s_0$ は $S$ の要素である。
- $s_0$ と $s_1$ を $S$ の要素とする。この時 $(s_0,s_1)$ は $(01,01),(01,11),(11,01),(11,11)$ の $4$ 通りであり、それぞれの場合において $s_0 \textrm{ AND } s_1$ は $01,01,01,11$ となる。従っていずれの場合も $s_0 \textrm{ AND } s_1$ は $S$ の要素である。
より $S$ は良いbit列集合です。
サンプル6
入力
2 2 01 10
出力
No
$S = \{01,10\}$ であり、$(s_0,s_1) = (01,10)$ と置くと $s_0$ と $s_1$ は $S$ の要素です。一方で $s_0 \textrm{ AND } s_1 = 00$ は $S$ の要素ではありません。従って条件3に反し、$S$ は良いbit列集合ではありません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。