解説によるとO(N2^N)でできるらしいけどO(N^2 2^N)でも通った。こっちは逆に2300点という点数の割にはかなり簡単に思える。
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int dp[(1<<21)+10][22];
int main()
{
memset(dp,0,sizeof(dp));
int n,K;cin>>n>>K;string s;
rep(i,n+1){
cin>>s;
rep(j,(1<<i)){
if(s[j]=='1') dp[(1<<i)+j][i]++;
}
}
for(int i=n;i>0;i--) rep(j,(1<<i)) rep(l,i+1){
if(dp[(1<<i)+j][l]<1) continue;
rep(k,l){
if(k+1<i && ((j&(1<<k))>>k)==((j&(1<<(k+1)))>>(k+1))) continue;
int to=(j>>(k+1)),bo=(j&((1<<k)-1));
dp[(1<<(i-1))+(to<<k)+bo][k]+=dp[(1<<i)+j][l];
}
}
for(int i=n;i>0;i--) rep(j,(1<<i)){
int sum=0;
rep(k,i+1) sum+=dp[(1<<i)+j][k];
if(sum>=K){
string out="";
rep(l,i){
out+=('0'+(j%2));j/=2;
}
reverse(All(out));
cout<<out<<endl;return 0;
}
}
cout<<""<<endl;
}