AtCoder ABC140 D - Face Produces Unhappiness (Go) - あるエンジニアのAtCoder奮闘記

irisruneです。青パフォを出すのはなかなか難しいですね。

問題

律儀にシミュレートしようとすると難しく思える問題ですが、解き方は意外と単純です。

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 minInt(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    var n, k int
    fmt.Scan(&n, &k)
    var s string
    fmt.Scan(&s)
    rs := append([]rune(s), 'L')

    count := n
    mode := 'R'
    for i, r := range rs {
        switch {
        case mode == 'R' && r == 'L':
            count--
            if i > 0 && i < n {
                count--
            }
            mode = 'L'
        case mode == 'L' && r == 'R':
            mode = 'R'
        }
    }

    fmt.Println(minInt(n-1, count+(2*k)))
}

結論から書くと、初期状態で幸福である人の数を $M$ とおくと $\max(N-1,M+2K)$ が解となります。計算量は $O(1)$ と言いたいところですが、初期状態で幸福である人の数を調べる処理がボトルネックとなるので $O(N)$ です。

まずはある人が幸福である条件を整理してみます。問題文では目の前に人がいて、かつ目の前の人が自分と同じ方向を向いている場合幸福であると定義されていますが、目の前に人がいないケースは両端の人にしか発生し得ません。そこで、 $1$ 番目の人の西隣に東を向いている人を、 $N$ 番目の人の東隣に西を向いている人を配置すれば、目の前に人がいるかどうか考える必要はありません。当然、追加で配置した人は幸福ではないことに注意が必要です。

次にどのように操作を行えば幸福である人を効率よく増やすことができるか考えます。例えば入力例1について考えてみましょう。入力例1の人の並びは以下の通りです。

LRLRRL

出力例1の解説では $(l,r)=(2,5)$ と選びましたが、 $(l,r)=(4,5)$ と選んだ場合を考えてみます。このとき操作後の人の並びは以下の通りです。

LRRRRL

このとき、西から2,3,4番目の人が幸福となり、出力例1と同様の結果が導き出せます。他に、 $(l,r)=(2,2),(3,3)$ のときも同様の結果が導き出せます。つまり、LR...RLあるいはRL...LRと表される区間の両端を除いた部分を反転させることにより幸福である人を効率よく増やすことができます。

...で省略された部分の内訳は問いませんが、LR...RLの内訳はすべてR、RL...LRの内訳はすべてLであるとおいても問題ないので以降はこのようにおきます。

幸福である人を効率よく増やすとここまで書いてきましたが具体的に何人ずつ増やすことになるか考えてみましょう。例えばLR...RLの両端を除いた区間を反転させることを考えます。するとLL...LLという並びになるわけですが、...の部分は反転を行ったところで幸福である人の人数は変わりません（これは...の内訳に関わりません）。一方で東側の2人は反転前は幸福でなかったのが反転後は幸福となり、全体で幸福である人の数は2人増えます。RL...LRについても同様です。

つまり操作1回ごとに幸福である人の数は2人増えるわけですが、どのようなケースについてこのような操作が行えなくなるか考える必要があります。実は操作を繰り返して辿り着くケースは次の4通りであることがわかります。

LL...LL

RR...RR

LL...LLRR...RR

RR...RRLL...LL

このうち1つ目と2つ目のケースは、幸福である人の数が $N-1$ となりこれ以上増やせないことがわかります。一方で3つ目と4つ目のケースは1回の操作で1つ目のケースまたは2つ目のケースに遷移させることが可能です。この操作で増える幸福である人の数は1人のみですが、幸福である人の数の上限を $N-1$ と定義しておくことで、2人増えるとみなすことができます。

ここまでの過程により、並んでいる人の人数、初期状態で幸福である人の数、操作可能な回数の3つがわかれば操作後に幸福である人の最大数が求められるようになりました。

最後に初期状態で幸福である人の数の求め方ですが、上記提出コードではRLという部分文字列の出現回数を数えることにより求めています。この部分文字列に相当する人はどちらも幸福ではないため、出現回数を2倍した数が幸福でない人の数となります。ただし両端の人については場合分けをせざるを得ません。序盤に書いたように両端に追加で人を配置して考えたとしても、追加した人は幸福ではないため結局場合分けが必要になってしまいます。

雑記

記事を書いていて気付きましたが、部分文字列の出現回数を数えるだけでよいので上記コードのようなややこしい処理をせずとも初期状態の調査は可能でしたね。
- stringsパッケージを用いればfor文を使う必要性すらありませんでした。