🐡

AtCoder Beginner Contest 296参加記（A～D）

2023/04/02に公開

AtCoder

競プロ

tech

AtCoder Beginner Contest 296に参加したので記録を書きます。
https://atcoder.jp/contests/abc296

今回も3完です。Dは解いておらず、なんかお気持ちだけ書いています。

A - Alternately

交互に並んでいるかどうかをそのままfor文で調べました。個人的にはこういうのでfor文を書いたら負けなんですが、いい感じの方法がパッと思いつかず。

fun main() {
    val n = readLine()!!.toInt()
    val s = readLine()!!

    var a = s.first()
    for(i in 1 until n) {
        if(a == s[i]) {
            println("No")
            return
        }

        a = s[i]
    }

    println("Yes")
}

B - Chessboard

これも調べるだけなのですが、数値のほうは下から数えた値になるのでちょっと混乱しました。

import kotlin.math.absoluteValue

fun main() {
    val s = List(8) {
        readLine()!!
    }

    for(i in 0 until 8) {
        for(j in 0 until 8) {
            if(s[i][j] == '*') {
                print((j + 97).toChar())
                println((i-8).absoluteValue)
                return
            }
        }
    }
}

C - Gap Existence

$Ai$ と $X$ はわかっているので、 $Aj$ が存在することを確認できればいいです。 $Ai - Aj = X$ を変形すると $Aj = Ai - X$ になります。この通りに $Aj$ を計算で求めた後、それを高速に探索できればいいことになります。
線形探索だと間に合わないのでソートして二分探索をしました。

fun main() {
    val (n, x) = readLine()!!.split(" ").map { it.toInt() }
    val a = readLine()!!.split(" ").map { it.toInt() }
        .sorted()

    for(i in 0 until n) {
        val aj = a[i] - x

        if(a.binarySearch(aj) > 0) {
            println("Yes")
            return
        }
    }
    println("No")
}

しかし、提出ボタンを押した直後に問題に気付いてWAを覚悟しました。

binarySearch()は見つかった場合はその位置（0-indexed）、見つからなかった場合は負の数を返しますが…

        if(a.binarySearch(aj) > 0) {
            println("Yes")
            return
        }

0は正常な結果としてあり得るのに、0より大きいかどうかを調べてしまっています。なので、値が0番目にある場合に不正に「No」を出力してWAとなってしまうはずでした。

しかし、そのままWAは出ず通ってしまいました。たまたまそれに該当するテストケースがなかったようですね…
まあ0番目といってもソート後の0番目であること、重複要素がある場合はどれが返るのかわからないこと、 $Ai$ に対する $Aj$ が他にもあるのであればそちらで引っかかって「Yes」になること、などいろいろあって漏れたのでしょうかね。

まあ、とにかく本来はこうあるべきだったはず…

fun main() {
    val (n, x) = readLine()!!.split(" ").map { it.toInt() }
    val a = readLine()!!.split(" ").map { it.toInt() }
        .sorted()

    for(i in 0 until n) {
        val aj = a[i] - x

        if(a.binarySearch(aj) >= 0) {
            println("Yes")
            return
        }
    }
    println("No")
}

もしくはSetを使うか。そのほうがわかりやすいし速いはずなのですが、なぜか二分探索を先に思いついてしまいました。

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

    val set = a.toSet()

    for(i in 0 until n) {
        val aj = a[i] - x

        if(aj in set) {
            println("Yes")
            return
        }
    }
    println("No")
}

なお、Cを解くのに10分以上かかっていました。この難易度にしてはちょっと遅いですね。

D - M<=ab

解けなかった問題ですが、なんか自分なりにいろいろ考察ごっこができて楽しかったです。内容としては的外れか、もしくは低次元だったので解ける可能性はなかったのですが。

なお、解説ACはできていません。解説の解読を試みましたが、途中で心折れました。
なぜそれが思いつくのかという点が全くわからない（たぶんそもそも書かれてもいない）ですが、それ以前に書かれている内容も理解できないのですよね…
たとえば $a$ について $⌈\sqrtM⌉$ までしか探索しなくていい理由について以下のように書かれていますが

$⌈\sqrtM⌉<a\leqb$ より、 $M\leq⌈\sqrtM⌉^2 <ab$ となり、このような2数の積が答えとなる事はないからです。

この1文の意味を理解するのに30分くらいかかっています。1文1文に対していちいちそれくらいかかるので、まさに「解読」のような作業になります。

$⌈\sqrtM⌉<a\leqb$ はまあ単なる仮定なのでいいとして、その場合になぜ $M\leq⌈\sqrtM⌉^2 <ab$ となるのかまずわからない。天井関数の意味がわかれば、まあ言われてみればたしかにそうだなという程度の認識には至りますが、理解が追いつくのに時間がかかります。

それがわかったとしても、「このような2数の積が答えとなる事はないからです。」の意味がまたわからない。 $⌈\sqrtM⌉^2$ が答えの候補として存在するので $ab$ は最小値ではあり得ないということですが、それを理解するのにもまた時間がかかる。

結局、仮定から論理的に（機械的に）導かれる結論が書かれているだけなので、理解もなにも書かれている通りじゃんという話かもしれないのですが、慣れていないと負荷が高いのですよ…
そもそも「仮定」「論理」「結論」みたいな整理ができるようになったのは最近論理学の本を少しかじったおかげで、その前は↑のような整理すらできなかったと思います。
まあそれがわかっても、負荷が高いと感じて疲弊し、時間もかかってしまうとなると途中で心折れるので実質読むことができない、となります。
なので、負荷が高いと感じなくなるまでひたすら読み解く訓練をするしかなさそうだなと思いました。
まあDPとかグラフの練習もしたいので優先順位が難しいのですが。

感想

Dのところでだいたい書いちゃいました。あらゆる力が足りないですが、その中でも解説の読解能力の低さは致命的だとあらためて思いました。知識を身に着けるためというより、読解能力を鍛えるという意味で、いろんな問題の解説を読み漁ったほうがいいような気がしますね…

（執筆時間: 51分6秒）

A - Alternately

B - Chessboard

C - Gap Existence

D - M<=ab

感想

Discussion