問題一覧 > 教育的問題

No.3311 Filter

レベル : / AI推定難易度 : 1100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 33
作問者 : 👑 p-adic / テスター : yu23578
お気に入りにしたユーザー ProblemId : 9371 / 自分の提出
問題文最終更新日: 2025-10-07 21:19:43
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 486 オムニバス (順位表) の他の問題:

Problem Statement

A string consisting only of the digits $0$ and $1$ is called a bit string.

You are given as input $2$ positive integers $N, M$ and a set $S$ with $M$ elements, consisting only of bit strings of length $N$.

 

The bitwise AND of bit strings of length $N$ is denoted by $\textrm{AND}$. $S$ is called a good bit string set if it satisfies all of the following $3$ conditions:

  1. The string of length $N$ consisting only of the digit $0$ is not an element of $S$.
  2. For any bit string $s_0$ of length $N$ and any element $s_1$ of $S$, if $s_0 \textrm{ AND } s_1 = s_1$, then $s_0$ is an element of $S$.
  3. For any elements $s_0$ and $s_1$ of $S$, $s_0 \textrm{ AND } s_1$ is an element of $S$.

 

Determine whether $S$ is a good bit string set.

Background

Let $I_N$ be the set of all positive integers less than or equal to $N$. For each $s \in S$, let $U_s$ be the set of all $i \in I_N$ satisfying the condition "the $i$-th character from the right of $s$ is $1$". By letting $\mathcal{F}_S$ be the family of sets $\{U_s \mid s \in S\}$, we can translate $S$ into the family $\mathcal{F}_S$ of subsets of $I_N$.

In set theory, topology, the theory of ordered sets, lattice theory and so on, the concept of a filter is often used. The property that $S$ is a good bit string set is equivalent to $\mathcal{F}_S$ being a filter on $I_N$, so this problem is essentially the problem of determining whether $\mathcal{F}_S$ is a filter on $I_N$.

Input

Number the elements of $S$ with the positive integers $m$ less than or equal to $M$, and denote them by $s_m$.

Then, the input is given from standard input in $1 + M$ lines in the following format:

  • Line $1$ contains $N, M$ separated by a single-byte space.
  • For each positive integer $m$ less than or equal to $M$, line $1 + m$ contains $s_m$.
$N$ $M$
$s_1$
$\vdots$
$s_M$

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $1 \leq N \leq 20$.
  • $M$ is an integer satisfying $1 \leq M \leq \min \{2^N,10^5\}$.
  • For any positive integer $m$ less than or equal to $M$, $s_m$ is a bit string of length $N$.
  • For any positive integers $m_0, m_1$ less than or equal to $M$, if $m_0 \neq m_1$, then $s_{m_0} \neq s_{m_1}$.

Output

Print Yes if $S$ is a good bit string set, and No otherwise.

Print a newline at the end.

Sample

Sample 1
Input
1 1
0
Output
No

We have $S = \{0\}$, and in particular the string $0$ of length $N = 1$ consisting only of the digit $0$ is an element of $S$. Therefore condition 1 is violated, and $S$ is not a good bit string set.

Sample 2
Input
1 1
1
Output
Yes

We have $S = \{1\}$, and:

  1. The string $0$ of length $N = 1$ consisting only of the digit $0$ is not an element of $S$.
  2. For any bit string $s_0$ of length $N = 1$ and any element $s_1$ of $S$, since $s_1 = 1$, we have $s_0 \textrm{ AND } s_1 = s_0$. Therefore, if $s_0 \textrm{ AND } s_1 = s_1$, then $s_0 = 1$, which is an element of $S$.
  3. For any elements $s_0$ and $s_1$ of $S$, since $s_0 = s_1 = 1$, we have $s_0 \textrm{ AND } s_1 = 1$, which is an element of $S$.

Hence $S$ is a good bit string set.

Sample 3
Input
2 1
10
Output
No

We have $S = \{10\}$. Letting $(s_0,s_1) = (11,10)$, $s_0$ is a bit string of length $N = 2$ and $s_1$ is an element of $S$. Furthermore, $s_0 \textrm{ AND } s_1 = s_1$ holds, but $s_0$ is not an element of $S$. Therefore condition 2 is violated, and $S$ is not a good bit string set.

Sample 4
Input
2 1
11
Output
Yes

We have $S = \{11\}$, and:

  1. The string $00$ of length $N = 2$ consisting only of the digit $0$ is not an element of $S$.
  2. Let $s_0$ be a bit string of length $N = 2$ and let $s_1$ be an element of $S$. Then, since $s_1 = 11$, we have $s_0 \textrm{ AND } s_1 = s_0$. Therefore, if $s_0 \textrm{ AND } s_1 = s_1$, then $s_0 = 11$, which is an element of $S$.
  3. Let $s_0$ and $s_1$ be elements of $S$. Then, since $s_0 = s_1 = 11$, we have $s_0 \textrm{ AND } s_1 = 11$, which is an element of $S$.

Hence $S$ is a good bit string set.

Sample 5
Input
2 2
01
11
Output
Yes

We have $S = \{01,11\}$, and:

  1. The string $00$ of length $N = 2$ consisting only of the digit $0$ is not an element of $S$.
  2. Let $s_0$ be a bit string of length $N = 2$ and let $s_1$ be an element of $S$. Then $s_1$ is either $01$ or $11$. If $s_0 \textrm{ AND } s_1 = s_1$, then $s_0$ is either $01$ or $11$ when $s_1 = 01$, and $s_0$ is $11$ when $s_1 = 11$. Therefore, in either case, $s_0$ is an element of $S$.
  3. Let $s_0$ and $s_1$ be elements of $S$. Then there are $4$ possibilities for $(s_0,s_1)$: $(01,01),(01,11),(11,01),(11,11)$, and in each case $s_0 \textrm{ AND } s_1$ is $01,01,01,11$, respectively. Therefore, in every case, $s_0 \textrm{ AND } s_1$ is an element of $S$.

Hence $S$ is a good bit string set.

Sample 6
Input
2 2
01
10
Output
No

We have $S = \{01,10\}$. Letting $(s_0,s_1) = (01,10)$, $s_0$ and $s_1$ are elements of $S$. On the other hand, $s_0 \textrm{ AND } s_1 = 00$ is not an element of $S$. Therefore condition 3 is violated, and $S$ is not a good bit string set.

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