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

はじめに

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

辞書式順序とは

• AtCoderのABC007b問題の出題文章に下記のように書かれている。
  • ある文字列 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問題を解いてみる。
• 問題の内容はシンプルで、与えられた文字列(a〜zを使用)より辞書式順序が前の文字を示せ、というもの。不可能な場合は-1を返す。
• 例えば、A="xyz"に対して「xy」が回答となる。「xyy」でも可。
• まあ、実際にコードを書くとすれば、A="a"の時だけ「−1」を返して、それ以外は「a」を返せば良い。アホみたいな問題だよね。

辞書式順序の問題（いきなりハードル上げてきた版）

• ABC009c問題を解いてみる。
• 問題の内容はシンプルで、与えられた文字列のうち、いくつかの文字の場所を入れ替えて、辞書式順序を最も小さくせよというもの。ちなみに、不一致が許容される最大文字数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」を作ってみた。
• この構造体Dazは、次のように使える。

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関数を利用して問題を解くコードは、以下の通り。

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の考え方を拝借しちゃってます。
• こんな解法を、コンテストの時間中に思いつく人って凄いなぁ。