問題一覧 > 通常問題

No.2669 Generalized Hitting Set

レベル : / AI推定難易度 : 2725 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 19
作問者 : suisen / テスター : cureskol chineristAC ygussany
お気に入りにしたユーザー ProblemId : 10176 / 自分の提出
問題文最終更新日: 2024-03-08 23:04:00
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 420 (順位表) の他の問題:

Note

The time limit and memory limit of this problem are set strictly, so using a fast language is recommended.

A PyPy implementation of the intended solution takes about 3,500 ms of execution time and about 210 MB of memory at runtime. A Java implementation of the intended solution takes about 2,000 ms of execution time and about 140 MB of memory at runtime. In particular, for PyPy both the time limit and the memory limit are extremely tight, so using another language is strongly recommended.

Problem Statement

You are given positive integers $n,m,k$ and sets $S _ 1, S _ 2, \ldots, S _ m\subseteq \lbrace 1,2,\ldots,n\rbrace$. Here, it is guaranteed that each $S _ i$ has at least $k$ elements.

For a set $T\subseteq\lbrace 1,2,\ldots,n\rbrace$, let $f(T)$ be the number of $i\in\lbrace 1,2,\ldots,m\rbrace$ satisfying $\lvert S _ i\cap T\rvert \geq k$.

For a positive integer $p\in\lbrace 1,2,\ldots,m\rbrace$, let $g(p)$ be the minimum number of elements of a set $T\subseteq\lbrace 1,2,\ldots,n\rbrace$ such that $f(T)\geq p$.

Find $g(p)$ for all $p=1,2,\ldots,m$.

Input

The input is given from standard input in the following format.

$n\ m\ k$
$S _ 1$
$S _ 2$
$\vdots$
$S _ m$

Here, $S _ i$ is given as a string of length $n$ consisting of 0 and 1. If the $j\ (1\leq j\leq n)$-th character of $S _ i$ is 0, then $j\notin S _ i$, and if it is 1, then $j\in S _ i$.

  • All numerical values in the input are given as integers.
  • $1\leq k\leq n\leq 24$
  • $1\leq m\leq 3\times 10 ^ 5$
  • $S _ i$ is a string of length $n$ consisting of 0 and 1
  • $S _ i$ contains at least $k$ occurrences of 1

Output

Output $m$ lines. On the $p\ (1\leq p\leq m)$-th line, output the value of $g(p)$.

Also output a newline after the $m$-th line.

Sample

Sample 1
Input
5 4 2
11001
00101
01110
10110
Output
2
2
3
4

This input represents $n=5,\ m=4,\ k=2$ and $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$.

For example, if we take $T = \lbrace 3,4\rbrace$, then $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$, so the values of $i$ satisfying $\lvert S _ i\cap T\rvert \geq k$ are the $2$ values $i=3,4$, that is, $f(T) = 2$. It can be shown that $T = \lbrace 3,4\rbrace$ has the minimum number of elements among all $T$ satisfying $f(T) \geq 2$, so $g(2)=2$. This $T$ is also one of those with the minimum number of elements among all $T$ satisfying $f(T) \geq 1$, so $g(1) = 2$.

As for $g(3)$, $T = \lbrace 3,4,5\rbrace$ has the minimum number of elements among all $T$ with $f(T) \geq 3$, so $g(3) = 3$.

As for $g(4)$, $T = \lbrace 1,3,4,5\rbrace$ and $T=\lbrace 1,2,3,5\rbrace$ have the minimum number of elements among all $T$ with $f(T) \geq 4$, so $g(4) = 4$.

In summary, $g(1) = 2,\ g(2) = 2,\ g(3) = 3,\ g(4) = 4$.

Sample 2
Input
3 7 1
001
001
010
010
011
101
110
Output
1
1
1
1
2
2
2

There may exist $i,\ j\ (i\neq j)$ such that $S _ i = S _ j$.

Sample 3
Input
10 10 5
1011101111
1110111101
0000110111
1010100111
0110110101
1111011101
0100111101
1011101101
1111011110
1011011011
Output
5
5
5
5
6
6
6
7
7
7

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