問題一覧 > 教育的問題

No.2270 T0 Space

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 44
作問者 : 👑 p-adic / テスター : 👑 qand MasKoaTS
お気に入りにしたユーザー ProblemId : 9068 / 自分の提出
問題文最終更新日: 2023-03-21 12:53: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 384 (順位表) の他の問題:

Note

This problem has a strict time limit and a large input size, so we recommend using a language and implementation capable of fast input and output.

The writer's solution takes 247[ms] in c++, 1879[ms] in PyPy3, and 4489[ms] in Python3 (that is, TLE ).

Problem Statement

You are given as input $2$ positive integers $N, M$ and a set $S$ with $M$ elements satisfying the following condition:

  • Every element of $S$ is a string of length $N$ consisting only of the digits $0$ and $1$.

 

First, let us introduce a term. We say that $S$ is a good bit string set if, for any positive integers $n_0$ and $n_1$ not exceeding $N$, the following condition holds whenever $n_0 \neq n_1$:

  • There exists $s \in S$ such that the $n_0$-th character from the right and the $n_1$-th character from the right of $s$ differ.

 

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

Background

Let $I_N$ be the set of all positive integers not exceeding $N$, for each $s \in S$ let $U_s$ be the set of all $i \in I_N$ satisfying "the $i$-th character from the right of $s$ is $1$", and let $\mathcal{O}_S$ be the family of sets $\{U_s \mid s \in S\}$. In this way, $S$ can be translated into the family $\mathcal{O}_S$ of subsets of $I_N$.

When geometry is formulated in modern set theory, the concept of a topological space is often used. When the pair $(I_N,\mathcal{O}_S)$ is a topological space, the property that $S$ is a good bit string set is called the $\textrm{T}_0$ property or Kolmogorov property of the topological space $(I_N,\mathcal{O}_S)$.

The $\textrm{T}_0$ property is one of the properties of topological spaces known as separation axioms, and it is a very weak property among the commonly used separation axioms. One commonly used property stronger than the $\textrm{T}_0$ property is the one called the $\textrm{T}_2$ property or Hausdorff property, which is frequently assumed when topological spaces are dealt with in geometry.

Input

Number the elements of $S$ by the positive integers $m$ not exceeding $M$, and denote them by $s_m$.

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

  • Line $1$ contains $N$.
  • Line $2$ contains $M$.
  • For each positive integer $m$ not exceeding $M$, line $2 + m$ contains $s_m$.

Constraints

The input satisfies the following constraints:

  • $N$ is an integer satisfying $1 \leq N \leq 2^8$.
  • $M$ is an integer satisfying $1 \leq M \leq \min \{2^N,2^{16}\}$.
  • For any positive integer $m$ not exceeding $M$, $s_m$ is a string of length $N$ consisting only of the digits $0$ and $1$.
  • For any positive integers $m_0, m_1$ not exceeding $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
Yes

Since there is no pair of $2$ distinct positive integers not exceeding $N = 1$, $S = \{0\}$ is a good bit string set.

For those familiar with topological spaces: $(I_N,\mathcal{O}_S) = (\{1\},\{\{\}\})$ does not satisfy $I_N \in \mathcal{O}_S$, so it is not a topological space. Therefore, $S$ being a good bit string set is not equivalent to $(I_N,\mathcal{O}_S)$ being a $\textrm{T}_0$ topological space.

Sample 2
Input
1
2
0
1
Output
Yes

Since there is no pair of $2$ distinct positive integers not exceeding $N = 1$, $S = \{0,1\}$ is a good bit string set.

For those familiar with topological spaces: $(I_N,\mathcal{O}_S) = (\{1\},\{\{\},\{1\}\})$ is both a discrete topological space and an indiscrete topological space.

For those familiar with algebraic geometry: $(I_N,\mathcal{O}_S)$ is a topological space homeomorphic to the affine scheme $\textrm{Spec}(\mathbb{Q}_p)$ associated with the field $\mathbb{Q}_p$ of $p$-adic numbers.

Sample 3
Input
2
1
11
Output
No

There is the pair $(n_0,n_1) := (1,2)$ of $2$ distinct positive integers not exceeding $N = 2$. On the other hand, $S = \{11\}$ has only the element $s := 11$, and the $n_0$-th character from the right and the $n_1$-th character from the right of $s$ are both equal to $1$, so $S$ is not a good bit string set.

Sample 4
Input
2
3
00
01
11
Output
Yes

Ignoring order, the only pair of $2$ distinct positive integers not exceeding $N = 2$ is $(n_0,n_1) := (1,2)$. Since the element $s := 01$ of $S = \{00,01,11\}$ differs at its $n_0$-th and $n_1$-th characters, $S$ is a good bit string set.

For those familiar with topological spaces: $(I_N,\mathcal{O}_S) = (\{1,2\},\{\{\},\{1\},\{1,2\}\})$ is a $\textrm{T}_0$ topological space that is not a discrete topological space.

For those familiar with algebraic geometry: $(I_N,\mathcal{O}_S)$ is a topological space homeomorphic to the affine scheme $\textrm{Spec}(\mathbb{Z}_p)$ associated with the ring $\mathbb{Z}_p$ of $p$-adic integers.

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