辞書式順序について【競技プログラミング】

# はじめに
- 辞書式順序なんて特に学ばなくても楽勝でしょ、と思っていたら、意外と分かっていなかったので、まとめてみた。

# 辞書式順序とは
- AtCoderの[ABC007b問題](https://atcoder.jp/contests/abc007/tasks/abc007_2)の出題文章に下記のように書かれている。
    - ある文字列 S={S1,S2,...,Sn}とT={T1,T2,...,Tm}について、辞書順比較した際に S＜T であるとは、次のどちらか一方の状態が成り立っていることを言う。
        - 任意の整数`i (1≦i≦min(n,m))`に関して、常にSi=Tiが成立し、かつ∣S∣＜∣T∣である。ただし∣X∣は文字列Xの長さを表すものとする。
        - 或る整数`i (1≦i≦min(n,m))`に関して、`1 ≦ j ≦ i−1` を満たすどの整数jに関してもSj=Tjが成立し、かつSi＜Tiが成立する
- 上記はわかりやすく例を使って言い換えれば、こうなる。
    - S="aabcdd"、T="aabcddef"は、Sの方が短い(n<m)が、Sは最初から終わりまで、Tの同位置の文字と同じ。この場合、Tの方が文字数の多いので、S<T。
    - S="aabcdefg"、T="aabdg"は、SとTは、j=1,2,3で同じ文字だけど、i=4でSi<Tiなので、S<T。これは、i=1でSi<Tiとなるようなケースでも成立する。例えば、S="azzz"、T="c"はS1<T1で、j<1は存在しないので検証不要で、S<Tとなる。

# 辞書式順序の問題（アホアホ版）
- [ABC007b問題](https://atcoder.jp/contests/abc007/tasks/abc007_2)を解いてみる。
- 問題の内容はシンプルで、与えられた文字列(a〜zを使用)より辞書式順序が前の文字を示せ、というもの。不可能な場合は-1を返す。
- 例えば、A="xyz"に対して「xy」が回答となる。「xyy」でも可。
- まあ、実際にコードを書くとすれば、A="a"の時だけ「−1」を返して、それ以外は「a」を返せば良い。アホみたいな問題だよね。

# 辞書式順序の問題（いきなりハードル上げてきた版）
- [ABC009c問題](https://atcoder.jp/contests/abc009/tasks/abc009_3)を解いてみる。
- 問題の内容はシンプルで、与えられた文字列のうち、いくつかの文字の場所を入れ替えて、辞書式順序を最も小さくせよというもの。ちなみに、不一致が許容される最大文字数Kが与えられ、その条件下で入れ替え可能。
- 例えば、文字列`abc`に対し、K=2の場合、`bac`や`acb`は許容されるが、`cab`や`bca`は許容されない。なお、どの入れ替えを行っても順序が大きくなってしまうので、何も入れ替えしないのが正解。
- 実際の入力例は以下の通り。
```
10 3 // 文字数N=10、不一致許容文字数K=3
helloworld // 文字列S
```
- ちょっと、方針を考えてみる。
    - 解答となる文字列をAとする。文字列Sは定数(let)で保持する。
    - Sを文字(a-z)毎の文字の数とする辞書型dicを作成する。例えば、S="zaba"のときは、`dic=["a":2,"b":1,"c":0,....,"z":1]`となる。
    - 当然、最初のステップは、1文字目にSの中で最も小さい文字(aに近い文字)i0を持って来ることだが、持ってきても良いかどうかを判定しなければならない。
    - A[0]にi0をもってこれるかどうか、以下のように検定する
        - dic[i0] -= 1 とする。(実際の文法では、`dic[i0,default:0] -= 1`と書く)
        - このとき、残りの文字列S[1...<(n-1)]をdic内の文字を使って、残りの不一致許容数K-1以下で再現できるかどうか？。再現できる場合は、i0を先頭に持ってきても良いと言うことになる。もし、i0で駄目なら、i0の次に小さい文字i1で同じことを順に検証していく。
    - 当然、上記はA[1]以降も同様のロジックで繰り返していく。
- ここで、キモは、dic内の文字を使って、不一致許容数(K-1)以下の条件で、文字列S[1...<(n-1)]を再現できるか？というロジックをどのように組むかだが、一般化して言えば、dic内の文字で、不一致許容数j以下で、文字列Tを再現できるか？という話になる。
- このロジックは、文字列Tについてもdic_Tを作り、dicとdic_Tの不一致文字数の絶対値の和の半分がj以下かどうか？で判定できる。
- 分かりづらいから、具体例を出すと、
    - 文字列①"aaab"と文字列②"abbb"の不一致文字数は2となっている。
    - これをそれぞれdic1とdic2に格納するとdic1=["a":3,"b":1]、dic2=["a":1,"b":3]となり、aの不一致数2とbの不一致数2を足すと4となっている。
    - よって、文字列①②の不一致数2は、dic1とdic2の不一致数4の半分となっている。
    - つまり、dic1とdic2の不一致数4の半分である2が不一致許容数j以下であればOKと言うことになる。
- 今回、二つのdicの不一致数を算出するための[構造体「Daz」を作ってみた](https://qiita.com/kei_tnk/items/32ed8ec76eddcf347a75)。
- この構造体Dazは、次のように使える。
```swift
var d1 = Daz("zaba")!
var d2 = Daz("aaab")!

print(d1.sorted) // [("a", 2), ("b", 1), ("z", 1)] -- 実体は辞書型だが、abc順のタプルとして表示（個数0の文字は非表示）
print(d1.diff(d2)) // 2 -- d1とd2の文字の差(aの文字数差1 + ｚの文字数差1)
```
- イニシャライザの後に「!」が付いているのは、引数が"aBc"のように、英小文字以外の文字を含むときにnilを返すため。
- このDazとdiff関数を利用して問題を解くコードは、以下の通り。
```swift
let (N,K) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let S = Array(readLine()!) // 要素はCharacter型(軽量)

struct Daz {...} // 省略

var dic = Daz(String(S))! // 使える文字の残り個数を辞書型で格納
var A:[Character] = [] // 回答を格納
var k = K // 不一致許容数

for i in 0..<N {

    var temp = dic.sorted // dicの要素を若い順のタプル(英小文字,文字数)の配列にする
    let dic_rS = Daz(String(S[(i+1)..<N]))! // rSはrest of S（Sの残り）の意味 -- 残り文字列の辞書型を用意
    
    for (c,_) in temp { // 小さい文字から使えるか検証

        var dic_next = dic
        dic_next.remove(c) // 検証対象となる「cを除いた残り文字dic_next」を用意

        // cで入れ替えて問題ないかを検証してOKなら入れ替える        
        if dic_next.diff(dic_rS) / 2 <= (S[i] == c ? k : k-1) { // i文字目を入れ替えても残り文字でやりくりできるなら、入替実行
            if S[i] != c {k -= 1}
            A.append(c)
            dic.remove(c)
            break
        } 
    } 
    
}

print(String(A))
```
- 提出したら5msだった。swiftの過去提出の中では現時点で最速。
- Pythonの最速は11msだったから、倍速です。圧倒的じゃないか、我が軍は！
- え？c++の最速？...1msっすね。サーセン。

# おわりに
- 久しぶりに、定型パターンのアルゴリズムを使わない、ステゴロ勝負でした。
- まぁ、自力で考えつくわけもないので、[けんちょんさんのHP](https://drken1215.hatenablog.com/entry/2023/05/06/013800)の考え方を拝借しちゃってます。
- こんな解法を、コンテストの時間中に思いつく人って凄いなぁ。