💭

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

2023/03/26に公開

AtCoder

競プロ

tech

AtCoder Beginner Contest 295に参加したので記録を残します。
https://atcoder.jp/contests/abc295

今回は3完です。自分にしては早く解けたのでレーティングとしてはそれなりにプラスです。
Dは解けず、コンテスト後に解説を見ました。

A - Probably English

[and, not, that, the, you]のリストを作って探索します。 any() contains()を組み合わせて見かけ上はループなしで実装しています。

"and, not, that, the, you".split(", ")のような書き方をしているのは、文字列の部分をコピペした結果をそのまま使うためです。一つ一つ括るのが面倒で。
実装の高速化のためだったのですが、なんか混乱してその結果をlistOf()に渡して二次元リストにしちゃってエラーを出したりして却って遅くなっちゃいました。アホです。

fun main() {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ")

    val list = "and, not, that, the, you".split(", ")
    if(a.any { list.contains(it) }) {
        println("Yes")
    } else {
        println("No")
    }
}

B - Bombs

マンハッタン距離とか言われても何のことかわかりません…が、問題文に求め方が書いてあったので助かりました。
全マスを探索すれば $r1$ と $c1$ はその時点で見ているマスの位置ですが、 $r2$ と $c2$ はどうやって特定するのかな？マンハッタン距離から逆算する？？とか考えていましたが、制約が緩いので単純に $r2$ と $c2$ も探索すればいいと気づきました。4重ループです。

注意が必要なのは、全ての爆弾が同時に爆発するので、空きマスを作る処理の時に他の爆弾を空きマスにしてしまってその爆弾を消すと不正な結果になるということですね。
今回は探索対象の盤面をコピーして解答用の盤面を作り、実際に書き換えるのは解答用の盤面だけとすることで対処しました。
（なにげに、これがパッと思いついて余計なバグを埋め込まなかったのは自分的にはファインプレーかもしれない…）

import kotlin.math.abs

fun main() {
    val (r, c) = readLine()!!.split(" ").map { it.toInt() }
    val b = List(r) {
        readLine()!!
    }

    val result = b.toMutableList().map { it.toCharArray() }

    for(i in 0 until r) {
        for(j in 0 until c) {
            if(b[i][j] != '.' && b[i][j] != '#') {
                val n = b[i][j] - '0'

                for(k in 0 until r) {
                    for(l in 0 until c) {
                        if(abs(i - k) + abs(j - l) <= n) {
                            result[k][l] = '.'
                        }
                    }
                }
            }
        }
    }

    println(result.map { String(it) }.joinToString("\n"))
}

C - Socks

ペアができたものを配列から除去していけばいい、という発想になりましたが、実際にいちいち削除していたら遅くて間に合わないです。そこで、ソートして前から見ていって、隣り合う要素が同じならペアということで探索位置のインデックスを追加的にインクリメントすれば同じことが実現できると思いました。

こういう添字操作はバグらせやすいのでけっこう怖かったですが、大丈夫でした。

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

    var ans = 0
    var i = 0
    while (i < n - 1) {
        if(a[i] == a[i+1]) {
            ans++
            i++
        }
        i++
    }
    println(ans)
}

C問題を解いた時点で2000位台で、自分にしては良い感じです。

D - Three Days Ago

これは解けなかった問題です。
愚直にやるなら、 $l$ と $r$ のあり得るパターンを全探索ですが、もちろん間に合いません。愚直解だと何度も同じ探索をすることになるので、一度全体を探索した時に何らかの情報を保存しておいて探索をスキップする、つまりDPっぽいやつで解けるのか？とか雑に考えていました。まあ重要なのは保存する「何らかの情報」って具体的に何だよということなんですが、それについては全然わからず。
というか、ある区間で何らかの情報を保存したとして、それを含むより広い区間の答えを求める際にそれを使い回せるかというと、できなさそうな気がしたのでやっぱりDPじゃないかもって思って、そのあたりで諦めました。

解説を見ましたが、やはりDPはやっていなくて、各文字の出現回数の偶奇の問題でした。区間に含まれる文字数が偶数個でないとダメなのはわかっていたものの、各文字の出現回数が全部偶数個でないといけない（逆にそれを満たせば絶対成り立つ）というところまでは頭が回らず。言われてみればたしかにそうなんですが…

fun main() {
    val s = readLine()!!

    val map = mutableMapOf<String, Long>()
    val array = IntArray(10)

    map[array.join()] = 1

    for(i in s.indices) {
        array[s[i] - '0']++
        array[s[i] - '0'] %= 2

        val key = array.join()
        map[key] = map.getOrDefault(key, 0) + 1
    }

    var ans = 0L
    for((_, x) in map) {
        ans += (x * (x - 1)) / 2
    }
    println(ans)
}

fun IntArray.join(): String {
    return this.joinToString("")
}

まあDはけっこう難しかったようで、解ける人はそんなに多くなかったことで結果的に私のレーティングは守られました…

感想

最近はそんなに熱心に精進ができていませんが、一応Streakをつなぐために1日1問くらいは解いていました。簡単な問題はけっこう枯渇してきているので多少は考えないといけない問題を解くことが多くて、1日1問とはいえ毎日やっていることで、簡単めな問題を解くスピードは少し上がってきている気がしました。
今回レーティングが守られたのはDが難しかったのもありますが、自分にしてはCまで解くスピードが速かったからでもありますので。まあ、何もしないよりは何かやったほうがいいという感じですかね。

Dの解説ACは一応解説を理解したつもりになってから何も見ずにコードを書いたので書き写しではないのですが、単に実装内容を記憶しただけかもしれません。（いつも通り）
解説をわかったような気になっても、結局どうすればそれを思いつくことができるようになるのかわからないので、本当は理解してないんだろうなという気がします。どうすれば理解に至るのか、というか「理解」とはそもそもどういう意味なのか…
類題を解いてみるとか、もしくは時間がたった後にもう一回解いてみるとかすればいいのかもしれませんが。

とりあえず偶奇に注目する問題はけっこうあるというのと、あとはその問題に関してどのような情報が解法を思いつく突破口になるかわからないので、何の役に立つのかわからない（気付いてない）情報でもできるだけ収集して整理してみるといいんですかね。
（各文字の出現回数は偶数個でないといけない、とか）

先週まではなんか疲労困憊という感じだったけど、少し元気が出たので自分には解けない問題を解けるようにするほうの練習もやりたいなと思うなどしました。

（執筆時間: 1時間1分24秒）

A - Probably English

B - Bombs

C - Socks

D - Three Days Ago

感想

Discussion