Tenka1 Programmer Contest 2019 C - Stones をGoで解こうとしたら罠にハマりました (Go,Kotlin)

irisruneです。最近コンテスト時間に予定が被ってて参加できないのがよくないですね。

アルゴリズム面は結論から言えば累積和を使いました。それで解けるはずだったんですけどね…

package main

import (
    "fmt"
)

func minInt(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

func main() {
    var n int
    var s string
    fmt.Scan(&n, &s)

    cumSum := make([]int, n+1)
    cumSum[0] = 0
    for i := 0; i < n; i++ {
        if []rune(s)[i] == '#' {
            cumSum[i+1] = cumSum[i] + 1
        } else {
            cumSum[i+1] = cumSum[i]
        }
    }

    minAns := n
    for i := 0; i <= n; i++ {
        ans := cumSum[i] + ((n - i) - (cumSum[n] - cumSum[i]))
        minAns = minInt(minAns, ans)
    }
    fmt.Println(minAns)
}

解き方の大筋は大体解説の通りです。

最終形として左から白い石が連続し、残りが黒い石であればよい。
最終形として考えられるのは高々 $N+1$ 通りである。
それぞれについて色を変える石の数を求めればよい。
最終形の白い石と黒い石の境目（端の場合もある）の左右について白い石と黒い石の個数がわかれば3.を求められる。
4.は黒い石の数について累積和を用いることで求められる。

といった形で解くことができます。計算量も $O(N)$ で問題ないはずなのでジャッジにかけてみましょう。

f:id:amifiable:20190422112752p:plain

f:id:amifiable:20190422112806p:plain

どうして…

仕方ないのでKotlinで書いたほぼ同じプログラムがこちらになります。

fun main(args: Array<String>){
    val n = readLine()!!.toInt()
    val s = readLine()!!

    val lCumSum = mutableListOf(0)
    for(i in 1..n) {
        lCumSum.add(lCumSum[i - 1] + if(s[i-1] == '#') 1 else 0)
    }

    var minAns = n
    for(i in 0..n) {
        val ans = lCumSum[i] + ((n - i) - (lCumSum[n] - lCumSum[i]))
        minAns = listOf(minAns, ans).min()!!
    }
    println(minAns)
}

GoのコードとKotlinのコードの相違点は

Goは文字列をrune配列にキャストしてから文字比較をしている。
Kotlinは累積和を求める際にリストに要素を順番に追加している。

このくらいしかなく、入力も2つしかないのでそこで差が付くとも考えられないですね。

ということは文字列をrune配列にキャストする操作が計算量大きいんでしょうか。そう思って急遽書き直してみました。

package main

import (
    "fmt"
)

func minInt(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

func main() {
    var n int
    var s string
    fmt.Scan(&n, &s)

    cumSum := make([]int, n+1)
    cumSum[0] = 0
    for i := 0; i < n; i++ {
        if s[i:i+1] == "#" {
            cumSum[i+1] = cumSum[i] + 1
        } else {
            cumSum[i+1] = cumSum[i]
        }
    }

    minAns := n
    for i := 0; i <= n; i++ {
        ans := cumSum[i] + ((n - i) - (cumSum[n] - cumSum[i]))
        minAns = minInt(minAns, ans)
    }
    fmt.Println(minAns)
}