問題一覧 > 通常問題

No.2669 Generalized Hitting Set

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 19
作問者 : suisen / テスター : cureskol chineristAC 👑 ygussany
5 ProblemId : 10176 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-08 23:04:00

注意

本問題の実行時間制限および メモリ制限 は厳しめに設定されているため、高速な言語の使用を推奨します。

想定解の PyPy 実装の実行時間は約 3,500 ms, 実行時使用メモリ量は約 210 MB です。また、想定解の Java 実装の実行時間は 約 2,000 ms, 実行時使用メモリ量は約 140 MB です。特に、PyPy については実行時間制限とメモリ制限の両方が非常に厳しくなっているので他の言語の利用を強く推奨します。

問題文

正整数 n,m,kn,m,k および集合 S1,S2,…,Sm⊆{1,2,…,n}S _ 1, S _ 2, \ldots, S _ m\subseteq \lbrace 1,2,\ldots,n\rbrace が与えられます。ここで、各 SiS _ i の要素数は kk 以上であることが保証されます。

集合 T⊆{1,2,…,n}T\subseteq\lbrace 1,2,\ldots,n\rbrace に対して、∣Si∩T∣≥k\lvert S _ i\cap T\rvert \geq k を満たす i∈{1,2,…,m}i\in\lbrace 1,2,\ldots,m\rbrace の個数を f(T)f(T) とします。

正整数 p∈{1,2,…,m}p\in\lbrace 1,2,\ldots,m\rbrace に対して、f(T)≥pf(T)\geq p なる集合 T⊆{1,2,…,n}T\subseteq\lbrace 1,2,\ldots,n\rbrace の要素数の最小値を g(p)g(p) とします。

全ての p=1,2,…,mp=1,2,\ldots,m に対して g(p)g(p) を求めてください。

入力

入力は以下の形式で標準入力から与えられます。

n m kn\ m\ k
S1S _ 1
S2S _ 2
⋮\vdots
SmS _ m

ここで SiS _ i は 0, 1 からなる長さ nn の文字列として与えられます。SiS _ i の j (1≤j≤n)j\ (1\leq j\leq n) 文字目が 0 のときは j∉Sij\notin S _ i であることを、1 のときは j∈Sij\in S _ i であることを表します。

  • 入力される数値は全て整数で与えられる。
  • 1≤k≤n≤241\leq k\leq n\leq 24
  • 1≤m≤3×1051\leq m\leq 3\times 10 ^ 5
  • SiS _ i は 0, 1 からなる長さ nn の文字列
  • SiS _ i は 1 を kk 個以上含む

出力

mm 行出力してください。p (1≤p≤m)p\ (1\leq p\leq m) 行目には g(p)g(p) の値を出力してください。

mm 行目の出力の後も改行してください。

サンプル

サンプル1
入力
5 4 2
11001
00101
01110
10110
出力
2
2
3
4

この入力は n=5, m=4, k=2n=5,\ m=4,\ k=2 および S1={1,2,5}, S2={3,5}, S3={2,3,4}, S4={1,3,4}S _ 1 = \lbrace 1,2,5\rbrace,\ S _ 2 = \lbrace 3,5\rbrace,\ S _ 3 = \lbrace 2,3,4\rbrace,\ S _ 4 = \lbrace 1,3,4\rbrace を表します。

例えば T={3,4}T = \lbrace 3,4\rbrace とすれば、S1∩T=∅, S2∩T={3}, S3∩T={3,4}, S4∩T={3,4}S _ 1\cap T = \emptyset,\ S _ 2\cap T = \lbrace 3\rbrace,\ S _ 3\cap T = \lbrace 3,4\rbrace,\ S _ 4\cap T = \lbrace 3,4\rbrace より ∣Si∩T∣≥k\lvert S _ i\cap T\rvert \geq k を満たす ii は i=3,4i=3,4 の 22 つであり、即ち f(T)=2f(T) = 2 です。T={3,4}T = \lbrace 3,4\rbrace は f(T)≥2f(T) \geq 2 を満たす TT のうち要素数が最小であることを示せるので、g(2)=2g(2)=2 となります。また、この TT は f(T)≥1f(T) \geq 1 を満たす TT のうち要素数が最小のものの一つでもあるため、g(1)=2g(1) = 2 となります。

g(3)g(3) について、T={3,4,5}T = \lbrace 3,4,5\rbrace は f(T)≥3f(T) \geq 3 なる TT のうち要素数が最小なので g(3)=3g(3) = 3 です。

g(4)g(4) について、T={1,3,4,5}T = \lbrace 1,3,4,5\rbrace や T={1,2,3,5}T=\lbrace 1,2,3,5\rbrace は f(T)≥4f(T) \geq 4 なる TT のうち要素数が最小なので g(4)=4g(4) = 4 です。

以上をまとめると g(1)=2, g(2)=2, g(3)=3, g(4)=4g(1) = 2,\ g(2) = 2,\ g(3) = 3,\ g(4) = 4 となります。

サンプル2
入力
3 7 1
001
001
010
010
011
101
110
出力
1
1
1
1
2
2
2

Si=SjS _ i = S _ j なる i, j (i≠j)i,\ j\ (i\neq j) が存在することがあります。

サンプル3
入力
10 10 5
1011101111
1110111101
0000110111
1010100111
0110110101
1111011101
0100111101
1011101101
1111011110
1011011011
出力
5
5
5
5
6
6
6
7
7
7

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