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

はじめに

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

例題

• 典型問題90の問題006
  

定番の武器（二次元配列nex[i][c]）

• けんちょんさんが極めて汎用性が高いと言って紹介しているので、そうに違いない！（他力本願）

• こんな配列です。
  • nex[i][c] ← 文字列 S(英小文字のみ) の i文字目以降で、文字c が出現する最小の添字(存在しない場合は-1)
    • 例：S="abcda"
      • nex[0]["a"] = 0
      • nex[1]["a"] = 4
      • nex[0]["d"] = -1
• swiftでの配列のindexは整数しか使えないから、上記みたいに["a"]のような書き方は出来ないので、新しく構造体を作るしかないね。まぁ、こんな感じのコードかな。

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文字で可能な辞書順最小)

• 解答方針は、下図の通りです。説明いるかな？
  
• 一応説明するね。最小の文字を走査するindex範囲をl..<rとすると
  • lは、初期値を「0」として、次は、ヒットした文字位置の一つ先
  • rは、初期値を「N-K+1」として、次は、一つ先
• ちなみに、制約は、$N,K≦10^5$だから、文字列を単純に配列化して走査すると、計算量がO(N･K)になり、$10^{10}$になるからTLEになるよ。
• さて、nexを使って解くと、下記コードになる。

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プロトコルに準拠させるために追加したものです。詳しくは、この投稿を参考にしてね。
• ちなみに、230ms程度でACでした。

別解

• 方針は、下図を同じ。
  
• 計算量削減方法にnexを使わない方法として、実は自分で最初に思いついたのが、ヒープだったよ。
• ヒープは最小値（または最大値）を高速に拾うのに適してるからね。
• でも、ヒープは、要素を追加することは出来るけど、要素を削除する機能はない（最小値or最大値をpopするだけ）から、例えば、上図で3文字目走査範囲外の0〜6のインデックスからも最小値をポップしてしまう。
• よって、ヒープに格納する要素を（文字列、インデックス）のタプルにして、インデックスが走査範囲外であれば排除できるように工夫した。
• 結果、以下のコードとなった。

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にするための構造体。詳しくは、この投稿を参考にして欲しい。
  • Heapを使うため、タプルをComparableにする必要があったから、無理やりCpTplを作ったけど、本当にswiftのクソ仕様には苦労させられます。
• さて、計算量を試算すると、Heapを作るための計算量がO(NlogN)で、popするための計算量がO(KlogN)になるから、トータルでもO(NlogN)と考えれば良いかな。で、提出したら、50ms以下でAC。別解の方が圧倒的に速いね。
• まぁ、$logN(N≦10^5)$と26(アルファベットの数)を比べたら、5倍くらいの差が付くのは整合性がとれているね。

さいごに

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