問題概要

問題文はこちらを参照してください。

何度復習しても解き方を忘れてしまいます。Javaなんですが、MLEでも苦労しました。

解法

辞書順で$K$番目のものを求めるので、'a'～'z'のそれぞれで始まる部分列の個数がわかると、その和が$K$を超えた時点の文字で始まるのが$K$番目のものだとわかります。同様に、その文字で始まる部分列の中で、全体で$K$番目にあたるものを、その文字を除いた部分列の個数の中から探せます。

つまり、文字列を先頭(左)から見ていって、例えば'a'が現れないうちは、それ以降の文字列から'a'で始まるものの数と同じになります。初めて$i$文字目に'a'が現れたとし、$i+1$文字以降の文字列からそれぞれ'a'～'z'で始まる部分列の数がわかっているとしたら、それの先頭に'a'を足した新しい部分列ができるので、それらの数を足したものになります。ただし、$i+1$文字以降で{'a'}という部分列があった場合、それに'a'を足した{'a','a'}という部分列としてカウントしているので、{'a'}という部分列分、1個増えることになります。

従って、文字列$s$の先頭から$i$文字目以降で、$j$という文字から始まる部分列の数を考えると、次のようになります。

漸化式の定義： $$dp[i][j-'a\ ']= \begin{cases}\displaystyle 1+\sum_{k='a\ '}^{'z\ '}dp[i+1][k-'a\ '] & (j=s[i])\\ dp[i+1][j-'a\ '] & (j\ne s[i]) \end{cases}$$

$dp[i][j-'a\ ']$：$i$文字目以降で、$j$という文字から始まる部分列の数
$(0\le i \le N,\ 'a\ '\le j \le 'z\ ')$

初期値：$i$は0-indexedとしたときに、$dp[N][j]=0$(全て0)

答えとなる部分列の求め方ですが、以下の方法で求めます

  1. 'a'から順番にその文字で始まる部分列の数を$K$から引いていく
  2. $K$を超えるところで、答えとなる部分列にその文字を加える
  3. その文字が現れるところまで$i$を進める
  4. $K$から1を引いて(上記で説明したその文字1文字だけの部分列分)次の文字から同様に1から繰り返す

もし、先頭の文字が'z'までいっても$K$を超えなければ答えは"Eel"となります。

途中で部分列の数はlongでもオーバーフローすると考えられるので、対策が必要です。$K$番目がどれかを探せばいいので、$K+1$以上の数は計算する必要がありません。$INF=K+1$として、それ以上は計算しないという対策をしました。

この辺はソースコードを見るか、ちゃんとフローチャートとか書かないと分かりにくいですね。。。

考察

同じ問題が出たとしても、解ける気がしません。その時は、このページを見ながら解きます。

ちなみに、JavaではMLEになりました。文字列が$10^5$を超えるので、自前でBufferedReaderをかまして読み込みをしているのですが、そのバッファサイズを減らさないとMLEになるくらいシビアな問題でした。