

Time Limit: 2 sec / Memory Limit: 256 MB
問題文
文字列の辞書式順序による比較についてはご存知だろうか?知らない場合は ABC007 の B 問題にその定義が載っているので読むとよいだろう。
今回は、この辞書式順序が重要な役割を果たす問題を解いてもらいたいと思う。
まず、英小文字(a-z
)のみからなる N 文字の文字列 S が与えられる。S = S_1,\,S_2,\,...,\,S_N の文字を並び替えて作れるような文字列 T = T_1,\,T_2,\,...,\,T_N のうち、辞書順で最小になるようなものを求めてほしい。
ただし、並び替え方には 1 つだけ制限がある。別に整数 K が与えられ、元から位置の変わった文字の個数を K 以下にしなければならない。つまり、S_i ≠ T_i となるような(文字が不一致となるような) i (1 ≦ i ≦ N)の個数が K 以下であるような並び替え方しかできない。
※この問題は普段の ABC の C 問題に比べ難しくなっています。下のボタンを押すことで、ヒントとしてこの問題を解くためのアイデアの説明を読むことができます。じっくり取り組んでみてください。
入力
入力は以下の形式で標準入力から与えられる。
N K S
- 1 行目には文字列の文字数を表す整数 N (1 ≦ N ≦ 100) と、位置を変えてよい文字数の上限を表す整数 K (0 ≦ K ≦ N) が与えられる。
- 2 行目には英小文字のみからなる N 文字の文字列 S が与えられる。
出力
S の文字を並び替えて作れるような文字列で、しかも元から位置の変わった文字の個数が K 個以下であるようなもののうち、辞書式順序で最も小さくなるような文字列を 1 行に出力せよ。
出力の末尾にも改行をいれること。
入力例1
3 2 abc
出力例1
abc
位置の変わった文字の個数は 2 以下 でなければならないので、まったく並び替えをしなくても構いません。
このケースでは、並び替えをまったくしない場合が最も小さくなります。
入力例2
7 2 atcoder
出力例2
actoder
-
まず、T の先頭の文字を
a
(元の文字列atcoder
のうち最も小さいアルファベット)にできるかについて考えます。- 今回は元から S の先頭の文字が
a
であるため、T の先頭の文字をa
にすることができます。(たとえば並び替えをまったくせず S = T とすれば、T の先頭の文字をa
にできることが確かめられます) - なので、T の 1 文字目が
a
に決まります。
- 今回は元から S の先頭の文字が
-
次に、2 文字目を
c
にできるかについて考えます。- T の最初の 2 文字が
ac
であるとすると、この時点で少なくともc
は元の位置から場所が変わっています。 - なので、S の 3 文字目以降である
coder
に対して、まだ T に使っていないアルファベットdeort
をうまく並べて、位置の変わった文字の個数を 1 以下にできるかどうかを考える必要があります。 - 今回は
deort
を並び替えてtoder
とすれば T =actoder
となって、位置の変わった文字の個数が 2 で済ませられます。 - よって 2 文字目が
c
と決まります。
- T の最初の 2 文字が
-
次に、3 文字目を
d
にできるかについて考えます。- T の最初の 3 文字が
acd
であるとすると、この時点でc
とd
は元の位置から場所が変わっています。 - なので、4 文字目以降ではこれ以上元の位置から文字を動かしてはいけないことになります。
- しかし、まだ T に使っていないアルファベット
eort
をどのように並べても、S の 4 文字目以降であるoder
とぴったり一致させることはできません。 - なので、3 文字目を
d
にすることはできません。
- T の最初の 3 文字が
-
d
がだめだったので、3 文字目にe
を使えるかを考えます。- さきほどの
d
の場合と同じように、3 文字目をe
にすることもできません。
- さきほどの
-
e
もだめだったので、3 文字目にo
が使えるかを考えます。- ...
- ...
このようにして最初の文字から順に、まだ使っていない文字のなかで最も小さいアルファベットが使えるかどうか?を順に試していくことで答えである actoder
に辿り着くことができます。
入力例3
7 7 atcoder
出力例3
acdeort
K = 7 なので、好きなように並び替えをして構いません。問題文にもあるように、この場合はアルファベット順に並べることで最小の文字列を作ることができます。
入力例4
10 3 helloworld
出力例4
dehloworll