🙆

ABC 122 C - GeT ACのメモ

2022/10/08に公開

AtCoder

競プロ

tech

目についたC問題を解いてみるの回です。今回はわりとすんなり解けました。

考察

処理時間のワーストケースを考えます。 $N$ も $Q$ も最大値で、 $li$ が全て最小値、 $ri$ が全て最大値であれば、愚直な実装だと $O(N^2)$ となり間に合いません。

ただ、その場合は全く同じ探索を $10^5$ 回行うことになります。なので、一度全て走査してから位置情報をいい感じに記録しておき、それを定数時間で問い合わせられるようにできればいかにも計算量を削減できそうな感じですね。

適切な前処理をすることで特定区間内の合計値を定数時間で求めることができるものとして累積和があります。今回の問題は文字列の中の特定区間内の"AC"の個数を求める問題なので、その個数を記録した配列についての累積和を作っておけば解けそうです。

実装

import java.io.PrintWriter

fun main() {
    val (n, q) = readLine()!!.split(" ").map { it.toInt() }
    val s = readLine()!!

    // "AC"の位置情報を記録する
    val bucket = IntArray(n)

    var startIndex = 0

    while (true) {
        val findIndex = s.indexOf("AC", startIndex)
        if(findIndex == -1) {
            break
        } else {
            bucket[findIndex] = 1
            startIndex = findIndex + 1  // 探索対象が2文字なので範囲外参照の心配はない
        }
    }

    // 累積和
    val bs = IntArray(n + 1)
    for(i in 0 until n) {
        bs[i+1] = bs[i] + bucket[i]
    }

    val br = System.`in`.bufferedReader()
    val out = PrintWriter(System.out)
    (0 until q).forEach { _ ->
        val (l, r) = br.readLine()!!.split(" ").map { it.toInt() }

        var ans = bs[r] - bs[l-1]
        // 区間がACのAまでだった場合の考慮
        if(r != n && s[r-1] == 'A' && s[r] == 'C') {
            ans--
        }

        out.println(ans)
    }
    out.flush()
}

"AC"の位置情報は"A"の位置に1を記録することとしています。StringのindexOf()を遣って調べます。indexOf()は第二引数で探索を開始する位置を指定できるので、それを使って最後まで探索します。

累積和の求め方は一般的な方法です。覚えてはいないのでググって調べました。
（参照したページに例題としてまさにこの問題が載っていました…が、見出しが見えただけで内容は全く見ていないのでセーフ）

注意が必要なのは、区間がAとCをぶった切った場合です。"AC"のうち"A"だけが区間内だと、1多くカウントしてしまうことになるのでその場合の考慮を入れています。
（ansが0だったらマイナスになるかもと考えてその考慮を入れたコードを再提出したりもしましたが、1多くカウントしてしまっている場合の考慮なのでそんなことは起こらないですね…）

さらにもう一つ。この問題は入出力が大量になりうるので、入力の受け取りにはBufferedReader、出力にはPrintWriterを使っています。
PrintWriterを使ったほうが速いのは、都度フラッシュをせず最後にまとめて行うからです。

BufferedReaderを使ったほうが速いのはなぜなのかよくわかりません。以前試したら速かったというだけで、実はブレただけで実際には特に変わらないという可能性もあります…ｗ

まあ十分余裕があるので良しとします。

考察

実装

Discussion