F - Simple Subsequence Problem Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 2300 点

問題文

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 文字目が等しいことを指します。

制約

  • 0 \leq N \leq 20
  • X_i(0\leq i\leq N) の長さは 2^i であり、0 と 1 のみからなる
  • 1 \leq K \leq |S|
  • K は整数である

入力

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

N K
X_0
:
X_N

出力

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

入力例 1

3 4
1
01
1011
01001110

出力例 1

10

S に属する文字列は、(空文字列),1,00,10,11,001,100,101,110 です。 これらのうち 4 つ以上の部分列となる最長の文字列のうち辞書順最小のものは、10 です。

入力例 2

4 6
1
01
1011
10111010
1101110011111101

出力例 2

100

入力例 3

2 5
0
11
1111

出力例 3




空文字列が答えになります。






Score : 2300 points







Problem Statement
You are given a set S of strings consisting of 0 and 1, and an integer K.


Find the longest string that is a subsequence of K or more different strings in S.
If there are multiple strings that satisfy this condition, find the lexicographically smallest such string.


Here, S is given in the format below:


    

  • The data directly given to you is an integer N, and N+1 strings X_0,X_1,...,X_N. For every i (0\leq i\leq N), the length of X_i is 2^i.
    • 

  • For every pair of two integers (i,j) (0\leq i\leq N,0\leq j\leq 2^i-1), the j-th character of X_i is 1 if and only if the binary representation of j with i digits (possibly with leading zeros) belongs to S. Here, the first and last characters in X_i are called the 0-th and (2^i-1)-th characters, respectively.
    • 

  • S does not contain a string with length N+1 or more.
    • 



Here, a string A is a subsequence of another string B when there exists a sequence of integers t_1 < ... < t_{|A|} such that, for every i (1\leq i\leq |A|), the i-th character of A and the t_i-th character of B is equal.











Constraints
    

  • 0 \leq N \leq 20
    • 

  • X_i(0\leq i\leq N) is a string of length 2^i consisting of 0 and 1.
    • 

  • 1 \leq K \leq |S|
    • 

  • K is an integer.
    • 

















Input
Input is given from Standard Input in the following format:


N K
X_0
:
X_N













Output
Print the lexicographically smallest string among the longest strings that are subsequences of K or more different strings in S.
















Sample Input 1
3 4
1
01
1011
01001110













Sample Output 1
10




The following strings belong to S: the empty string, 1, 00, 10, 11, 001, 100, 101 and 110.
The lexicographically smallest string among the longest strings that are subsequences of four or more of them is 10.














Sample Input 2
4 6
1
01
1011
10111010
1101110011111101













Sample Output 2
100
















Sample Input 3
2 5
0
11
1111













Sample Output 3



The answer is the empty string.