TDPC G - 辞書順

考え方

ABCで言うと、F問題級。

まず、前半戦として、この方法で作られる文字列数を数える方法を考える。

例えば "abacbc" で考えてみる。
これから作られる文字列で 'a' で始まるものの一例に "abc" がある。
これは、文字を拾う位置として $1+2+4$、$1+2+6$、$1+5+6$、 $3+5+6$ の $4$ 通りが考えられる。
しかしこの問題には、異なる位置から拾っても文字列自体が同じなら同じとみなす制約がある。
よって、これは拾う文字位置の辞書順が最も早い $1+2+4$ のパターンのみ考えることにしたい。

これは、次のように考えることができる。
$5$ 文字めの 'b' に対し、同じ 'b' が $2$ 文字目にも存在している。
よって、$2$ 文字目より前の文字からいきなり $5$ 文字目に進むことを禁止する。
同様に 'c' について、$4$ 文字目より前の文字からいきなり $6$ 文字目に進むことを禁止する。
また、'a' についても、$1$ 文字目より前（つまり空文字列の状態）から $3$ 文字目に進むことを禁止する。
すると、$1+2+6$、$1+5+6$、 $3+5+6$ の $3$ つは規定に違反することになる。
そして、拾う文字位置の辞書順が最も早い $1$ つのみがカウントされることになる。
この場合、'a' で始まる文字列数は、'a' が初めて登場するところを先頭とする文字列数そのものとなる。

これを利用すると、作られる文字列の数を数えることができる。
文字列の後ろから順に、動的計画法を進める。
DP中は、以下の $2$ つの情報をもつ。

• 各位置の文字ごとの、そこで始まる文字列数
• 各アルファベットの最前出現位置（実際には、後半用に配列などで全出現位置を持つとよい）

こうして、s の末尾から順に $1$ 文字ずつ追加していく。
追加した文字で始まる文字列数は、各アルファベットの最前出現位置での文字列数の合計 $+1$ すればよい。
$+1$ は、後ろが空文字列、つまりその文字 $1$ つだけの文字列の分。
毎回 $26$ 個愚直に足してもよいし、毎回 $1$ 個しか変化がないので差分更新を用いてもよい。
また、総数が $K$ より大きい値を細かく管理する意味はないので、全て $K+1$ に丸めておく。

いずれの方法でもとにかく追加した文字で始まる文字列数をテーブルに入れ、最前出現位置を更新する。
最終的に $1$ 文字目を追加した後、同様の集計をして $-1$ したものが総文字列数となる。
$-1$ するのは、空文字列の分。

以上で前半戦が終了。
この時点で文字列数が $K$ 個に届いていなければ、"Eel" を出力してプログラム終了。

以降は後半戦。
文字列数が足りている場合に、$K$ 番目を探索する方法。

まず、最初は基準位置を先頭とする。
そして、以下を繰り返す。

基準位置より後ろで各アルファベットが最初に登場する位置を調べる。
まず 'a' が最初に登場する位置での文字列数を見ると、それが、'a' である全文字列数である。
これが $K$ に届かない場合は、それらを全て採用した上で、'b' について同じ処理をする。
'b' でも届かなければ、それらも全て採用した上で 'c' に進む。
総数は足りているので、'z' までのどこかで採用数が $K$ 以上になる。

仮に 'c' で超えた場合は、以下のように処理をする。
まず、その 'c' で終わる文字列 $1$ つを採用する。
それでちょうど採用数が $K$ になったら探索を終了する。
足らない場合にはその 'c' の位置を新しい基準位置とした上で、再度 'a' から順に探索する。
出現位置を全て配列に収めていれば、新基準位置以前にある情報をはぎ取れば基準位置の更新ができる。

以上を繰り返し、毎回の $K$ 以上になった位置の文字を順につないだものが答えの文字列となる。

計算量は、アルファベットの文字数を $\sigma$ として $O(\sigma |s|)$。
Fenwick木を用いる等で工夫をすれば $O(\sigma +|s|\log \sigma)$ に高速化もできる。
ただし、定数倍が重くなることを考えると、実質的には高速化にならなさそうである。

入力例2での動作

入力を受け取る。

s: lexicographical
k: 100

後ろから順に、各位置の文字から始まる相異なる部分列の個数を求める。
dp[i] は、位置 $i$ の文字を最初に使ったときに作れる相異なる文字列数とする。

また、sum は現在見ている位置以降から作れる相異なる部分列の個数に、空文字を加えたものとする。
$K$ より大きい値を厳密に持つ必要はないので、$K+1=101$ を超える値は $101$ に丸める。

DP の結果は次のようになる。

最終的な sum は $101$ なので、空文字を除いても $100$ 個以上の相異なる部分列が存在する。

ここから、辞書順で $100$ 番目の文字列を前から決める。
残りの順位を count とする。

最初は count = 100。
a から始まる文字列は $64$ 個あるので、それらを飛ばして count = 36 とする。
次の c から始まる文字列は $101$ 個以上あるので、先頭の文字として c を採用する。
c 自体の分を引いて count = 35 となる。

同様に進めると、次のようになる。

文字を採用した後は、その位置より後ろにある文字だけを次の候補とする。
最終的に result は capal となる。

注意点

$K$ は $10^{18}$ まであるので、int 型からはみ出る。
long long 型を用いること。

部分列の個数は非常に大きくなる。
$K$ より大きい値を区別する必要はないので、$K+1$ を超えないように丸めて管理する。

別解

特になし。