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

AOJ 2022 : Princess, a Cryptanalyst

DP 文字列

練習で類題を解いたので解きました。

2・3年前にやって全く分からなかったけど今も解説見ないと分からなかった。

解法は同じ。

問題概要

  • N個の文字列が与えられます。( 1 <= N <= 10 )
  • N個の文字列全てを部分文字列とするような最小の文字数の文字列Sを作って下さい。
  • 文字数が同じ場合は辞書順最小の文字列を出力して下さい。

解法

  • dp[ 選んだ文字列の状態 ] [ 最後に選んだ文字列 ] = 最小の文字列
  • 文字列 a を 選んだ後に b を選んだ時に追加すべき文字列を予め用意しておく。
  • a = "abcad" b = "adfd" とすると marge( a -> b ) = "fd" ( "fd" を追加すればよい )
  • しかし、これだけでは "ABCD", "CDEF", " BCDEFG" などのパターンで
    この順番で併合していっても
    "ABCD" + "EF" + "BCDEFG" となってしまい最小に出来ません。
  • なので、予め"CDEF", "BCDEFG" のように他の文字列に完全内包されているような文字列は削除しておきます。
  • すると、上記のような反例が無くなりうまくいくようになります。
ソースコード

感想

解法で説明したような反例パターンが内包を消す方法が分からなかった。

というか他の文字列に完全に内包されてる文字列を消すだけでなんでOKになるのかよく分からなかった。(よくよく考えて見ると結構当然だった)

典型らしいのでちゃんと解けるようになれて良かった。