AtCoder AGC 037 A - Dividing a String (Go) - あるエンジニアのAtCoder奮闘記

irisruneです。ふとデザインを変えたいと思いましたが、ある程度まとまった時間を取らないと難しいですね。

問題

最多の分割を行うための方針は結構単純です。実は嘘解法と化していたことに後で気付きました。

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)
}

まず連続する2つの部分文字列が一致しないという条件を無視して考えてみると、明らかに1文字ずつに分割するのが最多の分割となります。では前述の条件を満たす分割についてはどうなるかというと、aaa...という文字列では以下のような分割を行うことが考えられます。

a aa a aa a aa ...

よって1文字あるいは2文字の部分文字列に分割すればよいとわかります。ここから分割の最大数¹を以下のアルゴリズムで求めることができます。

1文字目を基準点とする。
残りが1文字ならば当然分割をしない。
基準点と1文字先がそれぞれ違う文字ならば、その間で分割をして基準点を1文字進める。
基準点と1文字先が同じ文字ならば、
1. 残りが3文字以上ならば、その間で分割して更に2文字先と3文字先の間でも分割をし、基準点を3文字進める。
2. 残りが2文字ならば、分割をしない。
進めた基準点から再び2.～4.を行う。

このようにして解ける理由を2つの例を挙げて説明します。

1つ目の例はaaaaという文字列についてです。この文字列を頭から見ることを考えると、1文字目と2文字目が同じ文字であるため間で分割を行うかどうか選択することになります。ここで上記のアルゴリズムに反して分割を行わない場合、

aaa a

と分割するしかなくなります。これは明らかに、

a aa a

と更に分割することができ、結局1文字目と2文字目との間で分割を行うことが正しそうです。

2つ目の例はaaaaaという文字列についてです。これは上記のアルゴリズムが正しく成立しない例であり、実際に適用すると

a aa aa

となりますがこれは正しい分割ではありません。ただし、

a aaa a

と分割し直すことで条件を満たすようになり、しかも分割数も変わっていません。そのため、上記のアルゴリズムで求めた分割数をそのまま解とすることができます。嘘から出た真ですね。

上記コードでは逆に結合数を求めてから分割数を算出していますが、分割数をそのまま求めてもあまり変わらないと思います。

雑記

明日のコンテストは（多分）比較的得意なARC形式なのでいい結果を残したいですね。

後述しますが、正しい分割を求めているわけではありません。↩