AtCoder ABC 138 E - Strings of Impurity (Go)

irisruneです。久々に比較的易しめなE問題だった気はします。

問題

atcoder.jp

発想力が占める比重がかなり大きい気はします。

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    var s, t string
    fmt.Scan(&s, &t)

    structure := make(map[rune][]int)
    for r := 'a'; r <= 'z'; r++ {
        structure[r] = make([]int, 0)
    }

    for i, rs := range s {
        structure[rs] = append(structure[rs], i+1)
    }

    n := len(s)
    ans := 0
    for _, rt := range t {
        if len(structure[rt]) == 0 {
            ans = -1
            break
        }
        baseIndex := (ans % n) + 1
        var searchIndex int
        switch {
        case sort.SearchInts(structure[rt], baseIndex) == len(structure[rt]):
            searchIndex = n + structure[rt][0]
        default:
            searchIndex = structure[rt][sort.SearchInts(structure[rt], baseIndex)]
        }
        ans += searchIndex - baseIndex + 1
    }

    fmt.Println(ans)
}

まず考えるべきは、を連結する必要があるのかについてです。がを任意の個数連結した文字列の部分列となるためには、を構成するすべての文字がにそれぞれ1個以上含まれていることが必要十分条件です。よって、条件を満たすならばがを個連結した文字列の部分列であることは明らかです。

以上よりを高々個連結するだけでよいのですが、これでも文字列長がとなってしまうため普通に照合しては間に合いません。そこで、aからzまでの各文字がの何文字目に該当するかという情報を利用することを考えます。ここで各文字の位置情報をソートされた配列を用いて保持しておくと、基準となる位置より右に特定の文字が存在するか、また存在するなら何文字目かを二分探索を用いて調べることができます。つまり計算量は前処理を含めてで抑えられることがわかります。

ここまでくればあとは実装するだけですが、最終的な出力となる値との探索基準位置に剰余の関係を使うなど少しややこしいのでWAを出しやすいと思います。自分の場合はに同じ文字が2つ続く入力のテストができておらずWAを出していました（入力例2が該当しますが、出力が-1となるためテストケースとしては別物です）。

雑記

• Goの二分探索アルゴリズムに範囲指定の引数がないのは少し面食らいましたが、スライスで簡単に計算コストも少なく範囲指定できるので必要ないんですね。