けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Xmas Contest 2019 J - Sub-Post Correspondence Problem

信じる心が大切ですね

問題へのリンク

問題概要

 N 組の文字列  A_{i}, B_{i} が与えられる。 これらの組を好きな順序で好きな回数だけ選んで、 A 側と  B 側とをそれぞれ連結した文字列  S, T ができる。

このとき、 T S の部分文字列 (連続でなくてよい) とすることができるかどうかを判定せよ。

制約

  •  1 \le N \le 16

考えたこと

制約が不気味で、いかにも bitDP らしさを醸し出しているけど、実は関係ない。むしろこれは、受け取る文字列の長さの総和が  10^{5} 以下とか、いつもの制約を書かなくて済むようにこうなっているのかもしれない。

さて、自明にわかることとして

  • ある  i に対して、 T_{i} S_{i} の部分文字列となっているならば、 i のみを採用すればよい

ということがわかる。なので、そうでない反例が果たしてあるのかどうかを探ることとなる。実はないことがわかる。

AC コード

https://atcoder.jp/contests/xmascon19/submissions/9131067