D - Three Days Ago

[hxrxchang]

https://atcoder.jp/contests/abc295/tasks/abc295_d

問題概要

文字列自由にを並べ替えて同じ文字列が2度繰り返すことができるものを嬉しい文字列と呼ぶ。 文字列Sが与えられる。 Sの部分文字列 S[l:r+1]が嬉しい文字列になるl, rの組み合わせはいくつあるか求めよ。

解き方

文字列Sの長さは 5 * 10 ** 5。 l, r を決めるのに二重ループはできないので、計算量を削る方法を考える。

嬉しい文字列になるには、登場する文字すべての出現回数が偶数であることが条件になる。

ここから全く分からないかつ公式解説に書いてあることもすっと理解できなかったので、色々試してみた。

まずは公式解説にある通り、横を文字列S内の各文字(0~9)、縦をSの何文字目まで見たかを指す表で、その文字列が奇数回登場したら1、偶数回登場したら0になるように表を埋めていく。

入力例1の 20230322 だといきなりだと難しいので、2112 という文字列で考える。

2112 (l, r)が(1, 4)のとき、つまり2112は嬉しい文字列なのだが、表を見て規則性を考えると、すべて0になっている行に着目すればいい？と気づく。 つまり、すべて0である行の次の行がl, その後にすべて0である行がrになるということ？

この考えで、20230322 の表を埋めていくと以下になる。

先の考えで、すべて0になる行に着目すると(l, r)の組み合わせは、(1, 6), (1, 8), (7, 8) になる。 これが答えだと思ったが、(2, 7) も嬉しい文字列らしい。 "20230322[2:8]" は "023032" でたしかに嬉しい文字列であった。

もう一回表を見て、1行目、7行目を見ると同じになっていることがわかる！ つまり全て0ではなく、全て同じになっている行の組み合わせが、全ての文字の出現回数が偶数になっているということだ。

なので、表を埋めて行き、内容が全く同じになった行のその値と出現回数を求めmapで管理し、各mapのキーに対して、value(出現回数) Choice 2 をした合計が答えになる。 パリティの問題だった。

func solve() {
    _s := strToSlice(getStr(), "")
    s := make([]int, len(_s))
    for i := 0; i < len(_s); i++ {
        s[i] = s2i(_s[i])
    }

    table := make([][]bool, len(s) + 1)
    for i := 0; i < len(table); i++ {
        table[i] = make([]bool, 10)
    }

    for i := 0; i < len(s); i++ {
        j := s[i]
        copy(table[i+1], table[i])
        table[i+1][j] = !table[i+1][j]
    }

    mp := make(map[string] int)

    for _, v := range table {
        mp[sliceToStr(v, "")]++
    }

    cnt := 0
    for _, v := range mp {
        cnt += getComb(v, 2)
    }

    fmt.Println(cnt)
}

https://atcoder.jp/contests/abc295/submissions/54927641