ABC 122-C GeT AC (Kotlin)

irisruneです。先週のAGCはA問題早解きで1300出ないらしいしABCはD問題が難しすぎるし過酷ですね…

atcoder.jp

この問題は数列の部分和を求める問題と（ほぼ）等価です。つまり典型問題ですね。

あらかじめ数列（文字列）の先頭から各インデックスまでの累積和（解）を求めておくことで、 個のクエリそれぞれに対して解を時間で求めることができます。

fun main(args: Array<String>){
    val(n, q) = readLine()!!.split(" ").map(String::toInt)
    val s = readLine()!!
    val cumSum = mutableListOf(0)
    for(i in 1..(n - 1)){
        if(s.substring(i - 1, i + 1) == "AC") cumSum.add(cumSum[i - 1] + 1)
        else cumSum.add(cumSum[i - 1])
    }
    for(i in 1..q){
        val(l, r) = readLine()!!.split(" ").map(String::toInt)
        println(
            when {
                l == 1 -> cumSum[r - 1]
                s.substring(l - 2, l) == "AC" -> cumSum[r - 1] - cumSum[l - 2] - 1
                else -> cumSum[r - 1] - cumSum[l - 2]
            }
        )
    }
}

結論から言えば解説と同様に

println(cumSum[r - 1] - cumSum[l - 2])

で出力部分は事足ります。

今回一番悩んだのはこの部分で、累積和の差から解を求める際に左側の区切り位置がちょうど"AC"の間だった場合 1を引く必要があると考えた結果、上記のように出力部分が複雑になってしまいました。

実際は2文字セットで解を求めていく関係上、累積和のインデックスがズレるようです？ まだ今一つ理解しきれていません。

今回のコードレビューは特筆するほどでもないですが、

• 累積和を求める部分のif文でKotlin記法を用いて簡略化できる。
  • 出力部分のようにwhen文に置き換えることもできる（やってみると余計読みにくいという感想）。

雑記

• AGC032-Aについてはおそらく糸口は掴めているので近いうちに。
• ABC122-Dについては正直に言って解法がわかりません。愚直に場合の数を求めるのはほぼ不可能ですよね…