AtCoder AGC 019 B - Reverse and Compare (Go)

irisruneです。GoのLanguage Owner入りをのんびり目指していきたいです。

問題

atcoder.jp

除外して良いケースをどのように導き出すかという問題です。

package main

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

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

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.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    s := nextStr()
    n := len(s)
    cnt := make(map[rune]int)
    for _, r := range s {
        _, ok := cnt[r]
        switch {
        case ok:
            cnt[r]++
        default:
            cnt[r] = 1
        }
    }

    ans := 1 + (n * (n - 1) / 2)
    for _, c := range cnt {
        ans -= c * (c - 1) / 2
    }
    fmt.Println(ans)
}

両端の文字が同じ部分文字列を反転させることを考えます。部分文字列の長さが3以上であるとき、反転の結果生まれる文字列は両端の文字を除いた部分文字列を反転させた結果と同じ文字列となります。一方部分文字列の長さが2以下であるときは反転の結果生まれる文字列は元の文字列と同じ文字列となります。よって、両端の文字が同じ部分文字列は操作対象から除外していいケースということになります。

そのため、文字列から任意の2文字を取り出したとき両端の文字が同じとなる組み合わせの数を全体の組み合わせの数から引くことにより答えを求めることができます。同じ2文字を取り出す組み合わせ数は、文字列を構成する各文字種についてそれぞれ何文字存在するかをカウントすることで求めることができます。そのため、全体の組み合わせ数に反転操作を1回も行わない場合を含むことに気をつければ問題を解くことができます。計算量はとなります。

ところで、両端の文字が違う部分文字列の反転によって生まれる文字列は全て違う文字列になることを証明していませんが、簡単な例で操作をしてみることで直感的には示せるので、問題を解くだけならそれでよいと思います（厳密な証明は公式解説でされています）。

雑記

• 今週は企業コンテストが土曜日にあるので忘れずに参加したいです。