👌

AtCoder Beginner Contest 334参加記（A, B, D）

2023/12/24に公開

AtCoder

競プロ

tech

ユニークビジョンプログラミングコンテスト2023 クリスマス (AtCoder Beginner Contest 334)に参加したので記録を残します。
https://atcoder.jp/contests/abc334

今回はADの2完です。なんということでしょう。Bが難しすぎて頭爆発しました。しかしレート的には微増となりました。今回参加者が多かった気がしていて、それが影響したのかな？

A - Christmas Present

素直なA問題です。しかし、最初なぜか $B$ と $G$ を逆にしていてサンプルが合わず提出が微妙に遅れました。コンテスト前にテンション低かったのでコンデイションが良くなかったかも…

import kotlin.math.max

fun main() {
    val (b, g) = readln().split(" ").map { it.toInt() }

    val m = max(b, g)
    if(m == b) {
        println("Bat")
    } else {
        println("Glove")
    }
}

B - Christmas Trees

これが解けませんでした。粘ってましたが一旦諦めてDを解きに行って、Dが解けたので戻ってきてまた粘りました。
制約が小さければ全探索でいいのですが、B問題ってレベルの制約ではないので計算で求める必要がありそう。しかし計算は非常に苦手で…
まずは、ある地点 $x$ を考えたときに、 $x$ にツリーがあるかどうかを判定する方法を考えたのですが、それすらわからず。
なぜわからなかったかというと、 $A$ が0とは限らないので単純に $M$ の倍数かどうかを判定することはできないので…
としばらく考えてあと残り30分くらいかというタイミングで、それなら $A$ を0に補正しちゃえばいいじゃんということにようやく気づきました。 $A$ を0にしたら、 $L$ と $R$ も同じ分ずらせばいいだろうと。これで一気に霧が晴れたような感覚でした。

とはいえ、計算ができないことに変わりはないので意味不明な提出をしたりして時間を溶かしてタイムアップ。かなり惜しいところまでは行ったんですけどね。コンテスト後、特に解説は見ずにACまで持っていくことができました。

$A$ を0に補正したのであれば、あとは割り算で個数を求められます。ただ、 $L$ と $R$ のいずれも負の値であることがあり得るので場合分けしました。
あと負の数の割り算結果はよくわかってなくて怖いので、絶対値を割るようにしました。（理解すべきなんですが…）

どちらも正かどちらも負なのであれば、絶対値が大きいほうを $M$ で割った数から、小さいほうを $M$ で割った数を引きます。しかし、小さいほうが $M$ の倍数なのであれば余分に引いてしまうので、その場合は1を足して補正します。

$L$ と $R$ で正負が異なる場合は、それぞれの絶対値を $M$ で割った数同士を足します。また、0にもツリーがあるのでその分で1を足します。

そして、そもそも $L$ と $R$ が一致している場合は0なので別途判定して出力します。
…としていたのですが、それが最後の1ペナの原因でした…
$L$ と $R$ が一致している場合、まさにその地点にツリーもある場合は0でなく1になります。それを修正したらようやく通りました。

import kotlin.math.abs

fun main() {
    val (a, m, l, r) = readln().split(" ").map { it.toLong() }

    val ans = solve(a, m, l, r)
    println(ans)
}

fun solve(aa: Long, mm: Long, ll: Long, rr: Long): Long {
    val a = aa
    val m = mm
    var l = ll
    var r = rr

    if(a < 0L) {
        val absA = abs(a)
        l += absA
        r += absA
    } else {
        l -= a
        r -= a
    }

    if(l == r) {
        return if(abs(r) % m == 0L) {
            1
        } else {
            0
        }
    }

    if(r > 0 && l > 0) {
        val s = if(l % m == 0L) {
            1
        } else {
            0
        }

        return r / m - l / m + s
    } else if(r < 0 && l < 0) {
        val s = if(abs(r) % m == 0L) {
            1
        } else {
            0
        }

        return abs(l) / m - abs(r) / m + s
    } else if(r == 0L) {
        return abs(l) / m + 1
    } else if(l == 0L) {
        return r / m + 1
    } else {
        return abs(r) / m + abs(l) / m + 1
    }
}

解説のコードと比べるとはるかに冗長なのですけどね。解説のコードは簡潔すぎて驚きました。あるあるですが。

C - Socks 2

順位表より、CよりもDのほうが簡単そうだったので先にDを解いてからCの問題文をちゃんと読みました。少し考えた限りだとわからず。
再度順位表を見ると解けている人が少なく、その一方でBを解いている人は意外と多かったので、Bのほうを頑張ることにしてCは放棄しました。なのでこの問題はそこまで力を入れて考察できていないです。そのうちやるかもしれません。

D - Reindeer and Sleigh

ソリの質みたいなのは特に関係なく数が多ければいいので、方針としては単純に引くために必要なトナカイの数が少ないソリを優先して選ぶだけでよさそう。実装的には $R$ をソートして、小さいほうから順にトナカイが足りる限り選んでいけばいいです。
ソリを選ぶごとに残りのトナカイの数が減っていきますが、これはソリを選ぶごとに必要なトナカイの数が増えていくと考えると累積和で表せます。その累積和のうち、前から見ていったときに初めて $X$ を超える要素のときの一つ前のソリが最後に選ばれるソリなので、それが前から何個目かという値が答えですね。
$Q$ 回答える必要があるので線形探索だと間に合わないですが、ソート済なので二分探索で高速化すればいいですね。
このあたりは考察ってほどではなく、さっと思いつきました。

実装としては、二分探索は組み込みのbinarySearchを使いました。 $X$ で探索します。値が見つかればその位置が答え、見つからなかった場合は、仮に値があった場合はどの位置になるのかという値が取得できるので、その値の一つ前が答えです。

import java.io.PrintWriter

fun main() {
    val (n, q) = readln().split(" ").map { it.toInt() }
    val r = readln().split(" ").map { it.toLong() }
        .sorted()

    val cm = LongArray(n + 1)
    for(i in 0 until n) {
        cm[i+1] = cm[i] + r[i]
    }

    val br = System.`in`.bufferedReader()
    val out = PrintWriter(System.out)
    for(i in 0 until q) {
        val x = br.readLine().toLong()

        val tmpIndex = cm.binarySearch(x)
        val index = if(tmpIndex < 0) {
            -(tmpIndex + 1) - 1
        } else {
            tmpIndex
        }

        out.println(index)
    }

    out.flush()
}

あとは入出力は高速化します。地味にめんどう。

感想

Dがさくっと解けたのは嬉しかったですね。DというよりCくらいの難易度な気はしましたけども。以前解いた問題で、累積和と二分探索の組み合わせはわりとよくあると知ったのでそのおかげです。やはり、典型パターンを多くインプットするのが重要なんだろうな。暗記するだけでなく、ちゃんと使えるように仕上げる必要がありますが。
二分探索は最近けっこう使います。良いですよね、二分探索。困ったら二分探索できないかどうか考えると嬉しいことがあるかもしれない。
Bは惜しいところまでは行ったので残念でした。面倒な値は補正というのも典型パターンとして以前学習していたんですけどね、見事に忘れていました。典型とは言っても多すぎて、定着させるのは難しいものです。定着させるには、覚えたような気になるだけでなく類題を続けて解くなどしないとダメかもなあ。

とりあえず、今年のコンテストはこれで終わりですね。微増とはいえHighest更新で終わることができたのは良かったです。
なんだかんだで1年半くらい継続してくることができました。来年も頑張っていきます。
（執筆時間: 46分49秒）

A - Christmas Present

B - Christmas Trees

C - Socks 2

D - Reindeer and Sleigh

感想

Discussion