解法
何を全探索するか考える． 素直に \(T\) を全探索するのでは \(TLE\) ． \(T\) は全探索できないが，\(T\) の \(?\) の位置は，最大で \({}_{10}C_{5} = 252\)なので十分間に合う．
まず \(S := S_{i}\) を一つ固定して考える． \(?\) の位置だけ固定したとき， \(S\) から \(T\) を作れる条件を考える． \(j \in T.size()\) において，
- \(T_{j} = '?'\) なら，\(S_{j}\) は何でもよい．
- \(T_{j} \neq '?'\) なら，\(S_{j} = T_{j}\) が必要．
よって， 全ての \(j \in |T|\) with \(T_{j} = '?'\) と なる \(j\) に対して \(S_{j}\) を \('?'\) で置き換えて， \(S = T\) となることが，\(S\)から \(T\) を作れる必要条件． これが十分条件であることは明らか．
次に \(i \in N\) を動かして考えてみるが， これは全体で \(O({}_{L}C_{L/2} N)\) となる． ただし，\(S_{i}\) の一部を \(?\) で置き換えた文字列の個数をカウントするときに map を使っているので，オーダーに \(max_{i \in N} (|S|) log N\) が掛かる．
実装
\(?\) の取り方は bitmask を用いると簡単． \(?\) の選び方 \(\in 2^{L}\) のうち，popcount が \(K\) の物だけ使えばよい．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,l,k;
cin >> n >> l >> k;
ll ans = 0;
rep(msk, 1LL << l) if(pcntll(msk) == k){
vector<string> ns = s;
rep(i,n) rep(j,l) if(msk >> j & 1) ns[i][j] = '?';
map<string,ll> cnt;
rep(i,n) cnt[ns[i]]++;
for(auto [_,c]: cnt){
chmax(ans, c);
}
}
cout << ans << endl;
return 0;
}
