No.2669 Generalized Hitting Set
タグ : / 解いたユーザー数 19
作問者 :
cureskol
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
0and1 - $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もしくは右上の雲マークをクリックしてアカウントを作成してください。