Livedoorブログからの移動
はてなブログからの移動

E - Don't Be a Subsequence

解き方

  • 部分列でない最小の文字列の、先頭の文字を決める→2文字目以降の文字列について考える、を繰り返すDP
    • DPする時には、後ろから決めていかないといけない
    • どの文字を先頭にするか決めるために、どの文字がどこに現れるかについて前計算が必要

ハマったところ

  • 単純にこのDPが思いつかなかった
    • 辞書順最小に対しては、後ろからDPして、最後に経路復元するのが一つのテンプレートらしい。

github.com