AtCoder ABC 136 D - Gathering Children (Go)

irisruneです。日曜開催は予定を合わせるのが難しいです。

問題

atcoder.jp

大体こういう異様に大きな数字が出てきた時は剰余に注目すればよいですね。

package main

import (
    "bufio"
    "fmt"
    "os"
    "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 string
    fmt.Scan(&s)
    rs := []rune(s)
    n := len(rs)

    children := make([]int, n)

    cntR := 0
    for i := 0; i < n; i++ {
        switch {
        case rs[i] == 'R':
            cntR++
        case rs[i] == 'L':
            children[i] += cntR / 2
            children[i-1] += (cntR + 1) / 2
            cntR = 0
        }
    }

    cntL := 0
    for i := n - 1; i >= 0; i-- {
        switch {
        case rs[i] == 'L':
            cntL++
        case rs[i] == 'R':
            children[i] += cntL / 2
            children[i+1] += (cntL + 1) / 2
            cntL = 0
        }
    }

    for i := 0; i < n-1; i++ {
        fmt.Print(children[i])
        fmt.Print(" ")
    }
    fmt.Println(children[n-1])
}

この問題のポイントとしては、一定回数以上の操作を行うと2つの状態を交互に遷移するということです。具体的には、"RL"という部分文字列の出現する2つのマスで子どもの入れ替わりが起こり続け、それ以外のマスには子供がいないという形になります。

そのため、最終状態である回の移動を行った後の状態は、交互に遷移する2つの状態のうち偶数回の移動を行ったときの状態として表すことができます。

あとはそれをどう表現するかですが、2つの状態を交互に遷移するまで愚直に操作をシミュレートするという方法が一つ考えられます。しかし1回の操作に計算量がかかるとすると行うべき操作の回数は最悪でのため全体でとなり到底間に合いません。

動的計画法を用いてシミュレートすれば全体でに抑えられるらしいですが、そちらの方法は公式解説が詳しいです。今回は文字列を解析して最終状態を求める方法を取ります。

"RL"という部分文字列に着目するならば、文字列全体を"RR...RL...LL"という部分文字列に分割して考えても問題ありません。この場合初期状態で"R"のマスにいる子供については、"RL"からの距離が偶数のマスにいる子供は"R"のマス、奇数のマスにいる子供は"L"のマスに最終状態でいることになります（"RL"の"R"にいる子供は距離0とみなします）。同様のことが"L"のマスにいる子供についてもいえるので、計算量で最終状態を求めることができます。

なお、上記コードについては左端から右方向に"L"の連続する個数を数えて"R"が見つかった時に最終状態を更新し、右端から左方向に"R"の連続する個数を数えて"L"が見つかった時に最終状態を更新するという実装で、コードを単純化しています。左端が"R"、右端が"L"であることが制約条件で与えられているためその辺りのチェックが必要ないのは楽ですね。

雑記

• テンプレートだけ残っているいつもの標準入力受け取り部分ですが、前回前々回で触れたように長大文字列に対応していないので今回使っていません。
  • 長大文字列に対応した速い入力方法もあるようですが、横着してfmt.Scanを使っています。
• 来週は夏季休暇予定のため、1回更新するかしないかくらいになると思います。