💡

AtCoder Beginner Contest 265 A～Dのメモ

2022/08/24に公開

AtCoder

競プロ

tech

AtCoder Beginner Contest 265に出たのでメモを残しておきます。
https://atcoder.jp/contests/abc265

A - Apple

N個全てをX円で買う場合と、可能な限り3個ずつ買って端数をX円で買う場合の2パターンなので、そのうち小さい方が答えということで実装しました。

import kotlin.math.min

fun main() {
    val (x, y, n) = readLine()!!.split(" ").map { it.toInt() }
    val a = n * x
    val b = n / 3 * y + n % 3 * x
    println(min(a, b))
}

凡ミスで数分無駄にしました。計算力が低すぎますね…

B - Explore

実際に移動をシミュレーションして解きました。オーバーフローで1回WAを出しました。ちょっとでも怪しければLongにする癖をつける必要がありますね…

fun main() {
    val (n, m, t) = readLine()!!.split(" ").map { it.toInt() }
    val a = readLine()!!.split(" ").map { it.toInt() }
    val xy = List(m) {
        readLine()!!.split(" ").map { it.toInt() }
    }.toMutableList()

    var currentT = t.toLong()
    for(i in a.indices) {
        val tmpT = currentT - a[i]
        if(tmpT <= 0) {
            println("No")
            return
        } else {
            currentT = tmpT
        }

        if(xy.isNotEmpty() && xy[0][0] == i + 2) {
            currentT += xy[0][1]
            xy.removeAt(0)
        }
    }
    println("Yes")
}

残り時間は普通に大小関係を比較すればいいのに、引いた後に0以下になっているかどうか判定とかやっているのでわかりづらくなっています。
ループ内の前半と後半で「今いる部屋」という隠れた状態が変わる点が厄介です。ボーナス部屋かどうかの判定は移動後の部屋に対して行う必要があるのでi + 1、そしてiが0オリジンなので結果的に+ 2です。
解説コードだと余分な要素を入れることでiを1オリジンにしているんですね。なるほど。

C - Belt Conveyor

C問題にしては簡単だったので解けました。無限ループになっていないかどうかをどうやって判定すればいいか若干考えましたが、訪問済のマスに再度訪問したら絶対無限ループになるとわかったのであとはそのまま実装するだけでした。

fun main() {
    val (h, w) = readLine()!!.split(" ").map { it.toInt() }
    val G = List(h) {
        readLine()!!
    }

    val squares = G.mapIndexed { i, str ->
        str.mapIndexed { j, g ->
            Square(i, j, g, false)
        }
    }

    var i = 0
    var j = 0
    while (true) {
        val s = squares[i][j]
        if(s.visited) {
            println(-1)
            return
        } else {
            s.visited = true
        }

        when(s.cmd) {
            'U' -> {
                if(i == 0) {
                    println("${i + 1} ${j + 1}")
                    return
                } else {
                    i -= 1
                }
            }
            'D' -> {
                if(i == h - 1) {
                    println("${i + 1} ${j + 1}")
                    return
                } else {
                    i += 1
                }
            }
            'L' -> {
                if(j == 0) {
                    println("${i + 1} ${j + 1}")
                    return
                } else {
                    j -= 1
                }
            }
            'R' -> {
                if(j == w - 1) {
                    println("${i + 1} ${j + 1}")
                    return
                } else {
                    j += 1
                }
            }
        }
    }
}

data class Square(
    val i: Int,
    val j: Int,
    val cmd: Char,
    var visited: Boolean
)

println("${i + 1} ${j + 1}") が何度も出てくるあたりとかは良くないですが。

D - Iroha and Haiku (New ABC Edition)

Cを解いた時点でそれなりに時間は残っていましたが、Dは全然わかりませんでした。
以前、数列が来たらとりあえずソートしてみればいいんじゃね？と思ったことがあったのでソートしたらどうなるかを考えてみましたが全然的はずれでした。
愚直な実装では間に合うはずがないし、条件に合致する整数の組自体ではなく存在するかどうかだけ判定すればいいのでなんかいい感じの方法があるのだろうと思いましたがわかりませんでした。

おとなしく解説を見たところ累積和と二分探索で解けるということでしたが、よくわからなかったので一旦愚直実装をしてみることに。コンテスト中にやればよかったですね。

これでTLEとなり、少なくともWAは出ないことを確認しました。

fun main() {
    val line = readLine()!!.split(" ").map { it.toLong() }
    val n = line[0].toInt()
    val p = line[1]
    val q = line[2]
    val r = line[3]
    val a = readLine()!!.split(" ").map { it.toInt() }

    for(x in 0..(n - 3)) {
        for(y in (x + 1)..(n - 2)) {
            var tmpP = 0L
            for(i in x until y) {
                tmpP += a[i]
            }
            if(tmpP != p) {
                continue
            }

            for(z in (y + 1) until n) {
                var tmpQ = 0L
                for(i in y until z) {
                    tmpQ += a[i]
                }
                if(tmpQ != q) {
                    continue
                }
                for(w in (z + 1) .. n) {
                    var tmpR = 0L
                    for(i in z until w) {
                        tmpR += a[i]
                    }
                    if(tmpR == r) {
                        println("Yes")
                        return
                    }
                }
            }
        }
    }
    println("No")
}

これを段階的に改善していくアプローチです。まずは累積和です。累積和は名前だけは知っていましたが、どうやらこれを使えば配列の一部分の合計をO(1)で求められるということのようです。
累積和についてはこちらを参考にしました。

合計を計算で求められるのでたしかにO(1)です。

さて、とりあえず合計を求める箇所を累積和に置き換えてみます。

fun main() {
    val (tmpN, p, q, r) = readLine()!!.split(" ").map { it.toLong() }
    val n = tmpN.toInt()

    val a = readLine()!!.split(" ")
    // 累積和
    val s = mutableListOf(0L)
    a.forEach {
        s.add(s[s.size - 1] + it.toLong())
    }

    for(x in 0..(n - 3)) {
        for(y in (x + 1)..(n - 2)) {
            if(s[y] - s[x] != p) {
                continue
            }

            for(z in (y + 1) until n) {
                if(s[z] - s[y] != q) {
                    continue
                }
                for(w in (z + 1) .. n) {
                    if(s[w] - s[z] == r) {
                        println("Yes")
                        return
                    }
                }
            }
        }
    }
    println("No")
}

TLEは減りましたがまだダメなようです。まあ4重ループとかありますしね。

公式解説と、こちらの動画を参考にして考えを整理しました。いつもありがとうございます。

たぶんちゃんと理解はしていないのですが、一応わかったような気になったので現状の理解を書いてみます。
まず解説にある通り、満たすべき条件（一番上以外）は累積和により以下のように置き換えられます。

Sy - Sx = P
Sz - Sy = Q
Sw - Sz = R

さらにここから式を変形すると、以下のようになります。

Sy = Sx + P
Sz = Sy + Q
Sw = Sz + R

Sy、Szを右辺の式に置き換えるとこうです。

Sy = Sx + P
Sz = Sx + P + Q
Sw = Sx + P + Q + R

Sx、Sy、Sz、Swは累積和の配列の中のどこかにあるかもしれないやつですね。累積和の各要素数ループを回してSxと仮置きすれば、あとは上記の式の値が累積和の中に存在するかどうかを判定すればいいわけですね。
（最後のほうは見ちゃいけないかもしれませんが、Aiは1以上なので、見ても条件を満たす要素は絶対ないので、結果的には害はないでしょう）

それで、累積和の中に存在するかどうかを線形探索すると遅いので二分探索を使おうということですね。Aiは1以上なので、累積和の配列は単調増加ですので、ソート済なのと同じことなのでそのまま二分探索が使えます。
（二分探索はもともと知ってました）

KotlinではListにbinarySearchメソッドが生えているのでこれを使います。

fun main() {
    val (_, p, q, r) = readLine()!!.split(" ").map { it.toLong() }

    val a = readLine()!!.split(" ")
    // 累積和
    val s = mutableListOf(0L)
    a.forEach {
        s.add(s[s.size - 1] + it.toLong())
    }

    for(sx in s) {
        if(s.binarySearch(sx + p) > 0 &&
                s.binarySearch(sx + p + q) > 0 &&
                s.binarySearch(sx + p + q + r) > 0) {
            println("Yes")
            return
        }
    }

    println("No")
}

やったぜ

ちなみに、解説のコードではsetを使っていました。二分探索じゃないのではと思ったのですが、C++のsetはハッシュテーブルではなく平衡二分木での実装なので内部的に二分探索になるようです。

なお横に置いていたしていたx, y, z, wの大小関係ですが、累積和の配列は単調増加なので、条件の値が存在するとしたら絶対右側なので気にしなくていいようです。
ということなので、仮にsetがハッシュテーブルだとしても別に問題ないのでした。

計算量は二分探索はO(log N)、ハッシュテーブルの探索はO(1)なのでハッシュテーブルのほうが速いかもしれません。

試してみました。

fun main() {
    val (_, p, q, r) = readLine()!!.split(" ").map { it.toLong() }

    val a = readLine()!!.split(" ")
    // 累積和
    val s = mutableSetOf(0L)
    var crr = 0L
    a.forEach {
        crr += it.toLong()
        s.add(crr)
    }

    for(sx in s) {
        if(sx + p in s &&
            sx + p + q in s &&
            sx + p + q + r in s) {
            println("Yes")
            return
        }
    }

    println("No")
}

通ったけど速くなりませんでした。これが定数倍が遅いってやつですか。
なお、mutableSetOf関数で取得できるのはLinkedHashSetのようでした。HashSetにしたらどうなるかも一応試しましたがほとんど変わりませんでした。

感想

Cは解けましたが、いつもよりは簡単だったから解けただけなので、普通にCが解けるようになったわけではありません。これからも少しずつ力をつけていきます。
とはいえちょっとうれしいですね。いつもこのレベルだと張り合いがないですが、たまにデレてくれるくらいなら歓迎です。

Dはやはり難しいと思いました。アルゴリズムの知識が求められるほか、数式をこねくり回さないと解けないのでアルゴリズムを知っているだけでは解けません。まあ数学が普通にできる人からすると全然「こねくり回す」って次元じゃない可能性もありますが、数学ができない人からするとそういう感想になります。
累積和ですが、知っている人なら一瞬で発想するのだろうなあと思いました。添字の書き方とか露骨にそれっぽいです。

現状としては、わかっていたことではありますが、アルゴリズムの知識と数学力の両方が圧倒的に足りないと思いました。特に後者が鬼門です。
すごくそんな気はしていたので、実は算数レベルからやり直そうと参考書を買ったところでした。算数レベルはさすがに大丈夫じゃない？と思いますが、やってみたら案外ダメかもしれません。とりあえずやってみます。

まあ、「わかったような気になった」レベルとはいえ、段階的に理解を深めていくことができたのは良かったです。

教訓

オーバーフローに注意…
アルゴリズムを覚える
数学の勉強をする
解説がわからなかったら、愚直実装から始めて段階的に進めていく

A - Apple

B - Explore

C - Belt Conveyor

D - Iroha and Haiku (New ABC Edition)

感想

教訓

Discussion