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

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

TDPC (Typical DP Contest) G - 辞書順

いわゆる部分列を扱う DP ですね。経路復元も含んでいて少し難しい問題です。

問題概要

英小文字のみからなる長さ  N の文字列  S が与えられます。

 S の部分列 (連続でなくてもよい) として考えられる文字列をすべて考えたとき、その中で辞書順で  K 番目のものを求めてください。

制約

  •  1 \le N \le 10^{6}
  •  1 \le K \le 10^{18}

解法

この問題は、まさに「部分列を走査していく DP」の典型問題となっています。詳しくは次の記事で解説しています。

qiita.com