C - アメージングな文字列は、きみが作る!
Editorial
/
Time Limit: 3 sec / Memory Limit: 256 MB
問題文
あなたはDISCO社の面接を受けています。 あなたは面接官から「英小文字だけからなる文字列 S を与えるので、ある 3 種類の操作から 1 つ選んで行うということをちょうど K 回だけ行ってあなたが考えるアメージングな文字列を作ってください」というお題を与えられました。
許されている操作は以下の 3 つです。
- 文字列 S の i(1≦i≦|S|) 文字目を削除する。
- 文字列 S の i(1≦i≦|S|) 文字目を別の英小文字で置換する。
- 文字列 S の i(1≦i≦|S|+1) 文字目に好きな英小文字を挿入する。
あなたは、 K 回の操作で作ることが可能な文字列のうち辞書順で最小のものを作って面接官を驚かせることにしました。
ここで、ある文字列 X について、 |X| は文字列 X の長さを表すものとします。
また、ある文字列 s=s_1s_2s_3...s_n と t=t_1t_2t_3...t_m について、以下のどちらかを満たすとき、辞書順比較で s<t であるといいます。
- ある整数 i(1≦i≦min(n,m)) に関して、 1≦j<i を満たす任意の整数 j において s_j = t_j が成立し、かつ s_i<t_i が成立する。
- 任意の整数 i(1≦i≦min(n,m)) に関して s_i = t_i が成立し、かつ n<m が成立する。
入力
入力は以下の形式で標準入力から与えられる。
S K
- 1 行目に面接官から与えられた英小文字だけからなる文字列 S (2≦|S|≦300,000) が与えられる。
- 2 行目に行わなければならない操作回数を表す整数 K (1≦K≦|S|-1) が与えられる。
出力
S に対して K 回操作を行って作ることが可能な文字列のうち辞書順最小のものを 1 行に出力せよ。末尾の改行を忘れないこと。
部分点
この問題には部分点が設定されている。
- 2≦|S|≦10, 1≦K≦min(|S|-1,4) を満たすデータセットに正解した場合は 10 点が与えられる。
- 2≦|S|≦200を満たすデータセットに正解した場合はさらに 10 点が与えられる。
- 2≦|S|≦1,000を満たすデータセットに正解した場合はさらに 20 点が与えられる。
- 2≦|S|≦300,000を満たすデータセットに正解した場合はさらに 60 点が与えられ、合計 100 点が得られる。
入力例 1
abc 1
出力例 1
aabc
- S の先頭に
a
を挿入した文字列aabc
が 1 回の操作で作ることが可能な辞書順最小の文字列です。 - このケースは、 1 番目の部分点の制約を満たします。
入力例 2
abc 2
出力例 2
a
- S の 2 文字目と 3 文字目を削除した文字列
a
が 2 回の操作で作ることが可能な辞書順最小の文字列です。 - このケースは、 1 番目の部分点の制約を満たします。
入力例 3
acb 1
出力例 3
aab
- S の 2 文字目を置換した文字列
aab
が 1 回の操作で作ることが可能な辞書順最小の文字列です。 - このケースは、 1 番目の部分点の制約を満たします。