2021-08-10 TDPC (Typical DP Contest) G - 辞書順 AtCoder EDPCとTDPC 部分列DP 部分列 DP 復元 DP値を利用して状態復元 ナップサックDP 数え上げ問題 文字列 K番目を求める 辞書順 いわゆる部分列を扱う DP ですね。経路復元も含んでいて少し難しい問題です。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられます。 の部分列 (連続でなくてもよい) として考えられる文字列をすべて考えたとき、その中で辞書順で 番目のものを求めてください。 制約 解法 この問題は、まさに「部分列を走査していく DP」の典型問題となっています。詳しくは次の記事で解説しています。 qiita.com