問題概要
問題文はこちらを参照してください。
何度復習しても解き方を忘れてしまいます。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\ ']$:$i$文字目以降で、$j$という文字から始まる部分列の数
$(0\le i \le N,\ 'a\ '\le j \le 'z\ ')$
初期値:$i$は0-indexedとしたときに、$dp[N][j]=0$(全て0)
答えとなる部分列の求め方ですが、以下の方法で求めます
- 'a'から順番にその文字で始まる部分列の数を$K$から引いていく
- $K$を超えるところで、答えとなる部分列にその文字を加える
- その文字が現れるところまで$i$を進める
- $K$から1を引いて(上記で説明したその文字1文字だけの部分列分)次の文字から同様に1から繰り返す
もし、先頭の文字が'z'までいっても$K$を超えなければ答えは"Eel"となります。
途中で部分列の数はlongでもオーバーフローすると考えられるので、対策が必要です。$K$番目がどれかを探せばいいので、$K+1$以上の数は計算する必要がありません。$INF=K+1$として、それ以上は計算しないという対策をしました。
この辺はソースコードを見るか、ちゃんとフローチャートとか書かないと分かりにくいですね。。。
考察
同じ問題が出たとしても、解ける気がしません。その時は、このページを見ながら解きます。
ちなみに、JavaではMLEになりました。文字列が$10^5$を超えるので、自前でBufferedReaderをかまして読み込みをしているのですが、そのバッファサイズを減らさないとMLEになるくらいシビアな問題でした。