読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

SRM663 div.1 300 ABBADiv1

問題

ABBADiv1
A, Bのみからなる文字列initialとtargetが与えられる。このとき、initialに以下の2種類の操作を繰り返し行って、targetに変換できるか?

  • 文字列にAを付け加える
  • 文字列にBを付け加えて、文字列をひっくり返す

制約

 1 \le |initial| < |target| \le 50

解法

initialから変換していく途中の文字列は、targetもしくはreverse(target)に部分文字列として含まれていないといけない。
target、reverse(target)の部分文字列は合計O(|target|^2)個しか存在しないので、深さ優先探索で調べていけばよい。

コード

最大で49msだった。