AT_abc009_3 [ABC009C] 辞書式順序ふたたび

[problemUrl]: https://atcoder.jp/contests/abc009/tasks/abc009_3 文字列の辞書式順序による比較についてはご存知だろうか？知らない場合は [ABC007 の B 問題](http://abc007.contest.atcoder.jp/tasks/abc007_2)にその定義が載っているので読むとよいだろう。 今回は、この辞書式順序が重要な役割を果たす問題を解いてもらいたいと思う。 まず、英小文字（`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 問題に比べ難しくなっています。下のボタンを押すことで、ヒントとしてこの問題を解くためのアイデアの説明を読むことができます。じっくり取り組んでみてください。** ヒントを表示する 重要な点は、辞書順で最小を目指すときには **文字列の先頭にできるだけ小さいアルファベットがある方がよい** ということです。なので、まずは $ T $ の $ 1 $ 文字目をできるだけ小さいアルファベットにすることを考えましょう。 $ S $ の文字のうち、小さいアルファベットから順に $ T $ の先頭にできるかを試していって、最初にできるとわかった文字が $ T $ の $ 1 $ 文字目として決まります。次は残った文字のうち小さいものから順に $ T $ の $ 2 $ 文字目にできるか試していき、$ 3 $ 文字目、$ 4 $ 文字目と同様に決めていきます（入出力例2 でもう少し具体的な説明をしています）。 試すときに必要なのは「$ T $ をある文字列 $ t $ で始めることができるか？」を判定することです。これは、$ S $ のうちまだ $ t $ で使っていない文字をうまく並び替えて、$ S $ の後ろのほうとの文字の不一致の数をできるだけ少なくし、全体として不一致の数を $ K $ 以下にできるかどうかで判定できます。 たとえば $ S\ = $`program`、$ K\ =\ 3 $ で、$ T $ の最初 $ 3 $ 文字を `aro` にできるかを判定したいとします。このとき、すでに `aro` と $ S $ の先頭 $ 3 $ 文字 `pro` で不一致が $ 1 $ つあるので、残りの部分で不一致の数を $ 2 $ 以下にしないといけません。つまり、まだ使っていない文字 `pgrm` をうまく並び替えて、$ S $ の後ろのほうである `gram` との不一致の数をできるだけ減らして $ 2 $ 以下にできれば OK です。 この方法と、判定の部分を具体的にどうプログラムにするかについては自力で頑張ってみましょう。

N/A

N/A

### Sample Explanation 1 位置の変わった文字の個数は $ 2 $ \*\*以下\*\* でなければならないので、まったく並び替えをしなくても構いません。 このケースでは、並び替えをまったくしない場合が最も小さくなります。 ### Sample Explanation 2 \- まず、$ T $ の先頭の文字を `a` （元の文字列 `atcoder` のうち最も小さいアルファベット）にできるかについて考えます。 - 今回は元から $ S $ の先頭の文字が `a` であるため、$ T $ の先頭の文字を `a` にすることができます。（たとえば並び替えをまったくせず $ S\ =\ T $ とすれば、$ T $ の先頭の文字を `a` にできることが確かめられます） - なので、$ T $ の $ 1 $ 文字目が `a` に決まります。 - 次に、$ 2 $ 文字目を `c` にできるかについて考えます。 - $ T $ の最初の $ 2 $ 文字が `ac` であるとすると、この時点で少なくとも `c` は元の位置から場所が変わっています。 - なので、$ S $ の $ 3 $ 文字目以降である `coder` に対して、まだ $ T $ に使っていないアルファベット `deort` をうまく並べて、位置の変わった文字の個数を $ 1 $ 以下にできるかどうかを考える必要があります。 - 今回は `deort` を並び替えて `toder` とすれば $ T\ = $`actoder` となって、位置の変わった文字の個数が $ 2 $ で済ませられます。 - よって $ 2 $ 文字目が `c` と決まります。 - 次に、$ 3 $ 文字目を `d` にできるかについて考えます。 - $ T $ の最初の $ 3 $ 文字が `acd` であるとすると、この時点で `c` と `d` は元の位置から場所が変わっています。 - なので、$ 4 $ 文字目以降ではこれ以上元の位置から文字を動かしてはいけないことになります。 - しかし、まだ $ T $ に使っていないアルファベット `eort` をどのように並べても、$ S $ の $ 4 $ 文字目以降である `oder` とぴったり一致させることはできません。 - なので、$ 3 $ 文字目を `d` にすることはできません。 - `d` がだめだったので、$ 3 $ 文字目に `e` を使えるかを考えます。 - さきほどの `d` の場合と同じように、$ 3 $ 文字目を `e` にすることもできません。 - `e` もだめだったので、$ 3 $ 文字目に `o` が使えるかを考えます。 - ... - ... このようにして最初の文字から順に、まだ使っていない文字のなかで最も小さいアルファベットが使えるかどうか？を順に試していくことで答えである `actoder` に辿り着くことができます。 ### Sample Explanation 3 $ K\ =\ 7 $ なので、好きなように並び替えをして構いません。問題文にもあるように、この場合はアルファベット順に並べることで最小の文字列を作ることができます。