[AGC024F] Simple Subsequence Problem

有一个 `01` 串集合 $S$，其中每个串的长度都不超过 $N$，你要求出至少是 $S$ 中 $K$ 个串的子序列的最长串，如果有多解，输出字典序最小的那组解。 由于 $S$ 可能很大，因此我们是这样描述 $S$ 的： - 你将得到 $(N+1)$ 个 `01` 串，第 $i$ 个串的长度为 $2^{i-1}$。 - 第 $i$ 个字符串的第 $j$ 个字符，代表数字 $(j-1)$ 的、长度为 $(i-1)$ 的二进制表示是否出现在 $S$ 中。 $N \leq 20$。

[problemUrl]: https://atcoder.jp/contests/agc024/tasks/agc024_f `0`,`1` からなる文字列からなる集合 $ S $ と整数 $ K $ が与えられます。 $ S $ に属する異なる $ K $ 個以上の文字列の部分列であるような最長の文字列を求めてください。 条件を満たすものが複数ある場合、辞書順で最小になるものを求めてください。 ただし、$ S $ は以下の形式で与えられます。 - 整数 $ N $ と、$ N+1 $ 個の文字列が与えられる。$ N+1 $ 個の文字列は順に $ X_0,X_1,...,X_N $ であり、全ての $ i(0\leq\ i\leq\ N) $ に対し、$ X_i $ の長さは $ 2^i $ である。 - どの整数の組 $ (i,j)(0\leq\ i\leq\ N,0\leq\ j\leq\ 2^i-1) $ に対しても、$ X_i $ の $ j $ 文字目(ただし、最初の文字を $ 0 $ 文字目、最後の文字を $ 2^i-1 $ 文字目とする)が `1` であることと、$ j $ を(必要なら最初に $ 0 $ を補って) $ i $ 桁からなる二進表記で表してできる文字列が $ S $ に属することが同値である。 - 長さ $ N+1 $ 以上の文字列は、$ S $ には含まれない。 また、文字列 $ A $ が 文字列 $ B $ の部分列であるとは、ある整数列 $ t_1\ <\ ...\ <\ t_{|A|} $ が存在して、全ての $ i(1\leq\ i\leq\ |A|) $ に対し $ A $ の $ i $ 文字目と $ B $ の $ t_i $ 文字目が等しいことを指します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ X_0 $ $ : $ $ X_N $

$ S $ に属する異なる $ K $ 個以上の文字列の部分列であるような最長の文字列のうち、辞書順最小のものを出力せよ。

3 4
1
01
1011
01001110

10

4 6
1
01
1011
10111010
1101110011111101

100

2 5
0
11
1111

### 制約 - $ 0\ \leq\ N\ \leq\ 20 $ - $ X_i(0\leq\ i\leq\ N) $ の長さは $ 2^i $ であり、`0` と `1` のみからなる - $ 1\ \leq\ K\ \leq\ |S| $ - $ K $ は整数である ### Sample Explanation 1 $ S $ に属する文字列は、(空文字列),`1`,`00`,`10`,`11`,`001`,`100`,`101`,`110` です。 これらのうち $ 4 $ つ以上の部分列となる最長の文字列のうち辞書順最小のものは、`10` です。 ### Sample Explanation 3 空文字列が答えになります。