😺

ABC189 C - Mandarin Orangeのメモ

2022/09/16に公開

AtCoder

競プロ

tech

目についたC問題を解いてみるの回です。

マンダリンはスーパーでもよく見かけるオレンジですね。私もたまに食べます。

考察

この問題は要するにlからrまでの区間のうちの最小値 × 区間の長さ分のみかんを食べることができるということですね。最小値の倍数なので、区間を広げれば多く食べられるとは限りません。

まずは全探索するとどうなるか考えてみます。lとrについてそれぞれをループで回すこと（二重ループ）で全探索できます。lとrには大小関係がありますので、rはlの値が初期値となります。なので、計算量としてどう表せばいいのかよくわからないのですが、少なくともO(N^2)よりは小さくなります。Nの制約はN^4なので意外と大きくありません。おや、これは全探索でいけちゃうのでは？

区間が決まれば、あとは区間内の最小値 × 区間の長さを求めて、それの最大値が答えになります。
一旦これで提出してみます。

最初の提出

答えは大きくなるかもしれないのでLongを使います。

import kotlin.math.max

fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }
    var ans = 0L
    for(l in 0 until n) {
        for(r in l until n) {
            val range = a.subList(l, r + 1)
            ans = max(ans, range.min()!!.toLong() * range.size)
        }
    }
    println(ans)
}

まあ、ですよね…
min()によりコード上はカジュアルに最小値を取得できますが、たぶん線形探索してます。二重ループの中でさらにO(N)ではさすがに無理でしたね。

逆に言えば、ここを高速にできれば通るはずです。

最小値取得について考察

まず事前にソートしておけばO(1)で求められます。しかし、この問題はソートすると正しく結果が求められなさそうです。
たとえば(1, 4, 2, 5)とかだった場合、本来の答えは最後の(5)だけを取り出して5です。
しかしソートして(1, 2, 4, 5)にしてしまうと、(4, 5)を取り出した8が答えになってしまいます。

区間内で都度ソートなら結果は狂いませんが、おそらく線形探索より遅いので本末転倒です。なんかいい感じに事前処理して区間内の最小値を求める方法はないでしょうか？

それっぽいキーワードで検索してみると、Sparse Tableというデータ構造があることがわかりました。このデータ構造は構築にO(N log N)かかりますが、区間内の最小値の取得はO(1)で求められるということでした。まさに求めていたものです。これを使いましょう。

といっても自力実装などできませんのでどこかから拝借することになります。
結果としてはこちらから拝借しました。ありがとうございます。

~~IntelliJ IDEAにはJavaコードをKotlinコードに変換する機能があるんだ~~
~~なのでほぼコピペしただけだけどIntelliJ IDEAで警告が出るところだけは直したよ~~

二回目の提出

さてどうなるかな…

import kotlin.math.max

fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toInt() }
    val table = RMQSparseTable(a.toIntArray())
    var ans = 0L
    for(l in 0 until n) {
        for(r in l until n) {
            val range = a.subList(l, r + 1)
            ans = max(ans, a[table.query(l, r)].toLong() * range.size)
        }
    }
    println(ans)
}

class RMQSparseTable(A: IntArray) {
    var array: IntArray
    var logTable: IntArray
    var table: Array<IntArray>
    var num: Int

    init {
        num = A.size
        this.array = A.copyOf(num)


        //log_tableを前処理で作っておくことでクエリ処理時にO(1)でlogを計算できる
        logTable = IntArray(num + 1)
        for (i in 2 until num + 1) {
            logTable[i] = logTable[i shr 1] + 1
        }
        table = Array(num) { IntArray(logTable[num] + 1) }


        //table[i][2^0] = i番目の要素から長さ1の区間の最小値はA[i](A[i]自身か含まないので)
        for (i in 0 until num) {
            table[i][0] = i
        }
        var k = 1
        while (1 shl k <= num) {
            var i = 0
            while (i + (1 shl k) <= num) {
                val first = table[i][k - 1] //前部分
                val second = table[i + (1 shl k - 1)][k - 1] //後部分

                //前部分の最小値と後部分の最小値を比較して、より小さいものを採用する
                if (A[first] < A[second]) {
                    table[i][k] = first
                } else {
                    table[i][k] = second
                }
                i++
            }
            k++
        }
    }

    fun query(s: Int, t: Int): Int {
        //区間の長さ
        val d = t - s + 1
        //logの計算
        val k = logTable[d]
        return if (array[table[s][k]] < array[table[t - (1 shl k) + 1][k]]) {
            table[s][k]
        } else {
            table[t - (1 shl k) + 1][k]
        }
    }
}

通った！やったぜ！！

感想

まあ、理解せずコードを拝借していくスタイルだと、拝借したコードにバグがあった場合に解決できず詰むので良くないですね。
今回のコードはちょっと理解しようとする余力がないので将来の自分に託しますが、そのうちやりたいと思います。

それと、C問題でこのようなデータ構造が必須になるとは思えないので、あんまり想定された解法ではなさそうですね。

解説を見て

すごく簡素な実装で解けるようなので、やはり今回の解法は想定解とは違うようです。ただ、sparse tableでも解けるとは書いてあります。別解という感じですね。

気になったのが、計算量はO(N ^ 2)になるって書いてあります。よくわかってなさそう…

ただ、一応通ったことに満足してしまって解説内容を理解しようとする意欲が出ませんでした。今回はここまでにしておきます。

考察

最初の提出

最小値取得について考察

二回目の提出

感想

解説を見て

Discussion