Typical DP Contest G - 辞書順 - ツバサの備忘録

解法

まず、

$m_{i,j} = i$ 文字目の次に $j$ という文字が現れるインデックスの最小値

を計算します。
これは、 $m_{i-1,j} = m_{i,j}(j \neq s_{i}), m_{i-1,s_{i}} = i$ という更新を行えばよいです。
さて、

$dp[i] = i$ 文字目を先頭で使った際にできる、部分文字列の種類数

というDPを考えます。
$i$ 文字目を使った際に考えられるパターンは、

$i$ 文字目の1文字のみ
$i$ 文字目の次に、 $j$ という文字を繋げる

の2つです(後者は最大26通りありますが…)。前者は明らかにトータル1通りです。
後者については、 $i$ の直後に現れる $j$ を取ってくると、 $i$ 番目の文字の次に $j$ を置いたパターンの部分文字列が網羅できます。
なので、結局
$dp[i] = 1 + \sum_{j} dp[m_{i,j}]$
という遷移になります。
では、最終的に求めたい文字列はどうなるでしょうか。
まず、先頭の文字がa,b,...zであるような部分文字列全てについて足しても $K$ にならない場合は、明らかにEelとなります。
それ以外の場合は、前から貪欲、aから順番に見ていき、総和が $K$ 以上になるならその文字を選択…という操作を繰り返します。
実装の際は、先頭にダミーの文字を入れると実装が少し楽になります。

今見ているインデックスを $id$ として、次に選ぶ文字をaから順番に見ていきます。 $dp[m_{id,j}]$ を見て、これが $K$ 以上ならば $j$ が次の文字になります。そうでなければ、 $K$ から $dp[m_{id,j}]$ を引き、次の文字をチェックしていきます。
今見ている文字が最後の場合となるパターンを $K$ から引き忘れないようにすれば、答えが求まります。

感想

最近ABCやその他の場所で、ある状態を構成し数え上げる際に重複するパターンを、貪欲にチェックする操作のみ考慮することで重複を消す、という考え方を使ってきたので、それと似たような考え方でできました。
それよりむしろ、メモリ制限が厳しかったです…空間計算量はまだまだ難しいですね