AtCoder AGC 039 A - Connection and Disconnection (Go)

irisruneです。流石に残暑も落ち着いてきた感じです。

問題

atcoder.jp

単純に見えて意外と考えることが多い問題です。

package main

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

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 culculate(s string) int {
    rs := []rune(s)
    cnt := 0
    for i := 1; i < len(rs); i++ {
        if rs[i] == rs[i-1] {
            rs[i] = '*'
            cnt++
        }
    }
    return cnt
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    s, k := nextStr(), nextInt()

    switch {
    case k%2 == 0:
        s2 := strings.Join([]string{s, s}, "")
        s4 := strings.Join([]string{s2, s2}, "")
        ans2, ans4 := culculate(s2), culculate(s4)
        diff := ans4 - ans2
        fmt.Println(ans2 + (diff * ((k / 2) - 1)))
    case k%2 == 1:
        s3 := strings.Join([]string{s, s, s}, "")
        ans1, ans3 := culculate(s), culculate(s3)
        diff := ans3 - ans1
        fmt.Println(ans1 + (diff * (((k + 1) / 2) - 1)))
    }
}

ものすごく単純に見ると、文字列について必要な操作回数を求め、それを倍することになります。しかしを連結したときの繋ぎ目について考慮されていないのでこれは誤りです。では連結したときの繋ぎ目となる文字を見ればよさそうに思えますが、実際は繋ぎ目となる文字だけでなくその周辺の文字も見る必要があるため処理がやや複雑になりがちです。

そこで連結したときに必要な操作回数が何回増えるかを考えることにしてみます。つまり、について必要な操作回数とを個連結した文字列について必要な操作回数を求め、その差分を倍したものをについて必要な操作回数に足すことで解が求められそうです。しかしこれも以下のような入力例で誤りとなります。

aaa
3

文字列aaaについて必要な操作回数は回、文字列aaaaaaについて必要な操作回数は回、文字列aaaaaaaaaについて必要な操作回数は回となり、上記のアルゴリズムで求められる回という解は誤りであることがわかります。要するに、によっては文字列を個ずつ連結したときに増える操作回数が一定でないため、上記のアルゴリズムが適用できません。

少し考察すると、上記のアルゴリズムが適用できない例はが単一の文字で構成されていて、かつが奇数であるときに限られることがわかります。つまりを個連結した文字列を個ずつ連結したときに増える操作回数を求めれば、上記のアルゴリズムを少し変形することで解を求めることができます。当然の偶奇による場合分けが必要となりますが、連結の繋ぎ目について考えるよりは実装は簡単になると思います。

雑記

• B問題は解けそうで解けない微妙な状態です。