辞書順問題のお友達【競技プログラミング】

# はじめに
- 辞書式順序に関する問題において、定番と言える武器があるらしいので、使ってみたい。

# 例題
- [典型問題90の問題006](https://atcoder.jp/contests/typical90/tasks/typical90_f)
![](https://pbs.twimg.com/media/EyKfdNsVcAEuQa0?format=jpg&name=large)

# 定番の武器（二次元配列nex[i][c]）
- [けんちょんさんが極めて汎用性が高いと言って紹介している](https://drken1215.hatenablog.com/entry/2021/10/10/195200)ので、そうに違いない！（他力本願）

https://github.com/drken1215/algorithm/blob/master/String/next.cpp

- こんな配列です。
    - nex[i][c] ← 文字列 S(英小文字のみ) の i文字目以降で、文字c が出現する最小の添字(存在しない場合は-1)
        - 例：S="abcda"
            - nex[0]["a"] = 0
            - nex[1]["a"] = 4
            - nex[0]["d"] = -1
- swiftでの配列のindexは整数しか使えないから、上記みたいに["a"]のような書き方は出来ないので、新しく構造体を作るしかないね。まぁ、こんな感じのコードかな。
```swift
struct Nex{ // イニシャライズの計算量O(26N)
    let n:Int
    let data:[[Int]]
    
    init(_ S:String){
        let cs:[Character] = Array(S)    
        n = cs.count
        var ary = [[Int]](repeating:[Int](repeating:-1,count:26),count:n+1)
        for i in (0...(n-1)).reversed() {
            for j in 0..<26 {
                ary[i][j] = ary[i+1][j]
            }
            ary[i][Int(cs[i].asciiValue! - Character("a").asciiValue!)] = i
        }
        data = ary
    }
    
    subscript(_ i:Int,_ c:Character) -> Int{
        data[i][Int(c.asciiValue! - Character("a").asciiValue!)]
    }
}

let nex = Nex("abcda")
print(nex[0,"a"]) // 0
print(nex[1,"a"]) // 4
print(nex[0,"b"]) // 1
print(nex[2,"b"]) // -1
```
- 完成！

# 実際の利用方法
- 例題を解いてみる。入力は、次のような感じ。
```
14 5 // 文字数14、部分文字列の長さ5
kittyonyourlap // 文字列　⇒　答えは "inlap"(5文字で可能な辞書順最小)
```
- 解答方針は、下図の通りです。説明いるかな？
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2733720/6788f61d-4490-c937-3c12-e1d1c23c15be.png)
- 一応説明するね。最小の文字を走査するindex範囲をl..<rとすると
    - lは、初期値を「0」として、次は、ヒットした文字位置の一つ先
    - rは、初期値を「N-K+1」として、次は、一つ先
- ちなみに、制約は、$N,K≦10^5$だから、文字列を単純に配列化して走査すると、計算量がO(N･K)になり、$10^{10}$になるからTLEになるよ。
- さて、nexを使って解くと、下記コードになる。
```swift
extension Character: Strideable {･･･}
struct Nex{･･･}

let (N,K) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let S = readLine()!

var nex = Nex(S)

var ans:[Character] = []
var l = 0
var r = N-K+1
var k = 0

let a_z = Character("a")...Character("z") // Strideable準拠が必要
// let a_z = "a" as Character ... "z" -- この書き方は、AtCoderではエラーとなる

while k<K {
    for c in a_z{
        if nex[l,c] > -1 && nex[l,c] < r {
            ans.append(c)
            l = nex[l,c] + 1
            r += 1
            k += 1
            break
        }     
    }
}

print(String(ans))
```
- 上記の計算量は、nex作成でO(26N)、whileループでO(K･26）だから、トータルでもO(26N)と考えれば良いかな？まぁ、時間的には余裕ですね。
- そういえば、冒頭に`extension Character: Strideable {･･･}`があるけど、これは、Character型のレンジでforループを回したかったので、Strideableプロトコルに準拠させるために追加したものです。詳しくは、[この投稿](https://qiita.com/kei_tnk/items/2cc7c0e04ac7dbf0e60c)を参考にしてね。
- ちなみに、230ms程度でACでした。

# 別解
- 方針は、下図を同じ。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2733720/6788f61d-4490-c937-3c12-e1d1c23c15be.png)
- 計算量削減方法にnexを使わない方法として、実は自分で最初に思いついたのが、[ヒープ](https://qiita.com/kei_tnk/items/47f952f3053301faa265#%E3%83%92%E3%83%BC%E3%83%97)だったよ。
- ヒープは最小値（または最大値）を高速に拾うのに適してるからね。
- でも、ヒープは、要素を追加することは出来るけど、要素を削除する機能はない（最小値or最大値をpopするだけ）から、例えば、上図で3文字目走査範囲外の0〜6のインデックスからも最小値をポップしてしまう。
- よって、ヒープに格納する要素を（文字列、インデックス）のタプルにして、インデックスが走査範囲外であれば排除できるように工夫した。
- 結果、以下のコードとなった。
```swift
struct CpTpl<T:Comparable> : Comparable,CustomStringConvertible {･･･}

struct Heap<V:Comparable> : CustomStringConvertible {･･･}

let (N,K) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]
let cs = Array(readLine()!)

var ts:[CpTpl<Character>] = [] // タプルをComparableにするため、CpTpl型にする

for (i,v) in cs.enumerated() { 
    ts.append(CpTpl(v,i)) // タプル(英小文字,インデックス)の配列をつくる。
}

var heap = Heap(Array(ts[0..<(N-K)]),maxHeap:false) // 最小ヒープを作る。

var ans:[Character] = []
var l = -1 // lは最後にヒットした最小文字の位置

for r in (N-K)..<N {
    heap.insert(ts[r]) // ヒープの要素を追加する
    while true {
        let c = heap.popRoot()!
        if c.i > l { // ポップした値が走査範囲(i > 前回ヒット位置)の時だけ生かす
            ans.append(c.t)
            l = c.i
            break
        }
    }
}

print(String(ans))
```
- 上記コードの冒頭に、`struct CpTpl<T:Comparable>`があるけど、これはタプルをComparableにするための構造体。詳しくは、[この投稿](https://qiita.com/kei_tnk/items/871c71ffe84b7caf12a2)を参考にして欲しい。
    - Heapを使うため、タプルをComparableにする必要があったから、無理やりCpTplを作ったけど、本当にswiftのクソ仕様には苦労させられます。
- さて、計算量を試算すると、Heapを作るための計算量がO(NlogN)で、popするための計算量がO(KlogN)になるから、トータルでもO(NlogN)と考えれば良いかな。で、提出したら、50ms以下でAC。別解の方が圧倒的に速いね。
- まぁ、$logN(N≦10^5)$と26(アルファベットの数)を比べたら、5倍くらいの差が付くのは整合性がとれているね。

# さいごに
- この投稿の主題である、けんちょんさんのnexの使い方は理解できたから、目的は果たされた。
- それに、ギリで時間が足りない場合は、ヒープでちょっとだけ速くなることも確認できたから良かったよ。
- あとは、swiftの不満解消のために書いた2投稿（[タプルをComparableプロトコルに準拠させる一工夫](https://qiita.com/kei_tnk/items/871c71ffe84b7caf12a2)、[CharacterをStrideableプロトコルに準拠させる一工夫](https://qiita.com/kei_tnk/items/2cc7c0e04ac7dbf0e60c)）が活躍してくれたから、言うこと無しだね。