問題一覧 > 教育的問題

No.2270 T0空間

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 42
作問者 : 👑 p-adicp-adic / テスター : 遭難者遭難者 MasKoaTSMasKoaTS
0 ProblemId : 9068 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-21 12:53:43

注意

この問題は実行時間制限が厳しく入力サイズも大きいので、高速な入出力が行える言語・処理系の利用を推奨します。

writer解はc++で247[ms]、PyPy3で1879[ms]、Python3で4489[ms](つまり TLE )となっています。

問題文

入力に 22 個の正整数 N,MN, M と、次の条件を満たす要素数 MM の集合 SS が与えられます:

  • SS の任意の要素は数字 0011 のみからなる長さ NN の文字列である。

 

まずは用語を導入します。SS が良いbit列集合であるとは、NN 以下の任意の正整数 n0n_0n1n_1 に対し、n0n1n_0 \neq n_1 ならば次の条件が成り立つということです:

  • ある sSs \in S が存在して、ss の右から n0n_0 文字目と右から n1n_1 文字目が異なる。

 

SS が良いbit列集合であるか否かを判定してください。

背景

NN 以下の正整数全体の集合を INI_N と置き、各 sSs \in S に対し「ss の右から ii 文字目が 11 である」を満たす iINi \in I_N 全体の集合を UsU_s と置き、集合族 {UssS}\{U_s \mid s \in S\}OS\mathcal{O}_S と置くことで、SSINI_N の部分集合の集合族 OS\mathcal{O}_S に翻訳することが出来ます。

近代集合論で幾何学を定式化する際にはしばしば位相空間という概念が使われます。組 (IN,OS)(I_N,\mathcal{O}_S) が位相空間である時、SS が良いbit列集合であるという性質を位相空間 (IN,OS)(I_N,\mathcal{O}_S) T0\textrm{T}_0 性やコルモゴロフ性と呼びます。

T0\textrm{T}_0 性は位相空間の性質の中でも分離公理と呼ばれるものの1つで、よく使われる分離公理の中でも非常に弱い性質となります。T0\textrm{T}_0 性より強い性質でよく使われるものの1つに T2\textrm{T}_2 性やハウスドルフ性と呼ばれるものがあり、これは位相空間を幾何学で扱う際に頻繁に仮定される性質となります。

入力

SS の要素を MM 以下の各正整数 mm で番号付けし sms_m と置きます。

この時、入力は次の形式で標準入力から 2+M2 + M 行で与えられます:

  • 11 行目に NN が与えられます。
  • 22 行目に MM が与えられます。
  • MM 以下の各正整数 mm に対し、2+m2 + m 行目に sms_m が与えられます。

制約

入力は以下の制約を満たします:

  • NN1N281 \leq N \leq 2^8 を満たす整数である。
  • MM1Mmin{2N,216}1 \leq M \leq \min \{2^N,2^{16}\} を満たす整数である。
  • MM 以下の任意の正整数 mm に対し、sms_m は 数字 0011 のみからなる長さ NN の文字列である。
  • MM 以下の任意の正整数 m0,m1m_0, m_1 に対し、m0m1m_0 \neq m_1 ならば sm0sm1s_{m_0} \neq s_{m_1} である。

出力

SS が良いbit列集合である場合はYesと出力し、そうでない場合はNoと出力してください。

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

サンプル

サンプル1
入力
1
1
0
出力
Yes

N=1N = 1 以下の互いに異なる 22 正整数の組は存在しないため、S={0}S = \{0\} は良いbit列集合です。

位相空間を知っている人向けに言うと、(IN,OS)=({1},{{}})(I_N,\mathcal{O}_S) = (\{1\},\{\{\}\})INOSI_N \in \mathcal{O}_S を満たさないので位相空間ではありません。従って SS が良いbit列集合であることと (IN,OS)(I_N,\mathcal{O}_S)T0\textrm{T}_0 位相空間であることは同値ではありません。

サンプル2
入力
1
2
0
1
出力
Yes

N=1N = 1 以下の互いに異なる 22 正整数の組は存在しないため、S={0,1}S = \{0,1\} は良いbit列集合です。

位相空間を知っている人向けに言うと、(IN,OS)=({1},{{},{1}})(I_N,\mathcal{O}_S) = (\{1\},\{\{\},\{1\}\}) は離散位相空間かつ密着位相空間です。

代数幾何を知っている人向けに言うと、(IN,OS)(I_N,\mathcal{O}_S)pp 進数体 Qp\mathbb{Q}_p に付随するアフィンスキーム Spec(Qp)\textrm{Spec}(\mathbb{Q}_p) と同相な位相空間となります。

サンプル3
入力
2
1
11
出力
No

N=2N = 2 以下の互いに異なる 22 正整数の組として (n0,n1):=(1,2)(n_0,n_1) := (1,2) があります。一方で S={11}S = \{11\} は要素を s:=11s := 11 しか持たず、ss の 右から n0n_0 文字目と右から n1n_1 文字目は等しく 11 であるため SS は良いbit列集合ではありません。

サンプル4
入力
2
3
00
01
11
出力
Yes

N=2N = 2 以下の互いに異なる 22 正整数の組は順序を無視すれば (n0,n1):=(1,2)(n_0,n_1) := (1,2) しかありません。そして S={00,01,11}S = \{00,01,11\} の要素 s:=01s := 01n0n_0 文字目と n1n_1 文字目が異なるので、SS は良いbit列集合です。

位相空間を知っている人向けに言うと、(IN,OS)=({1,2},{{},{1},{1,2}})(I_N,\mathcal{O}_S) = (\{1,2\},\{\{\},\{1\},\{1,2\}\}) は離散位相空間でない T0\textrm{T}_0 位相空間となります。

代数幾何を知っている人向けに言うと、(IN,OS)(I_N,\mathcal{O}_S)pp 進整数環 Zp\mathbb{Z}_p に付随するアフィンスキーム Spec(Zp)\textrm{Spec}(\mathbb{Z}_p) と同相な位相空間となります。

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