信じる心が大切ですね
問題概要
組の文字列
が与えられる。
これらの組を好きな順序で好きな回数だけ選んで、
側と
側とをそれぞれ連結した文字列
ができる。
このとき、 が
の部分文字列 (連続でなくてよい) とすることができるかどうかを判定せよ。
制約
考えたこと
制約が不気味で、いかにも bitDP らしさを醸し出しているけど、実は関係ない。むしろこれは、受け取る文字列の長さの総和が 以下とか、いつもの制約を書かなくて済むようにこうなっているのかもしれない。
さて、自明にわかることとして
- ある
に対して、
が
の部分文字列となっているならば、
ということがわかる。なので、そうでない反例が果たしてあるのかどうかを探ることとなる。実はないことがわかる。