🗂

AtCoder Beginner Contest 286 A～Dのメモ

2023/01/22に公開

AtCoder

競プロ

tech

ウルシステムズプログラミングコンテスト2023（ABC286）に参加したので記録を残します。
本番ではA、B、Dが解けて、Cはわからなかったのでコンテスト後に解説を見てACしたものです。

A - Range Swap

$P$ から $Q$ までを要素に持つ配列と、 $R$ から $S$ までを要素に持つ配列とをそれぞれ作って一つずつ見ていき、2つの配列のうち同じ位置にある2つの値を使って入れ替えを行えばいいです。
（制約から、2つの配列の大きさは必ず同じです）

Kotlinだと配列ではなくRangeを使うと楽なのでそうしています。

import java.util.Collections

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

    for(pair in (p..q).zip(r..s)) {
        Collections.swap(a, pair.first - 1, pair.second - 1)
    }
    println(a.joinToString(" "))
}

難しいという意見もけっこう見ましたが、まあRangeとかzipとかswapとかがなければたしかにちょっと大変かもしれません。

B - Cat

これは文字列を置換するだけです。大抵の言語なら、組み込みのメソッドでも使えば一発です。

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

    println(s.replace("na", "nya"))
}

C - Rotate and Palindrome

残念ながら解けなかったやつです。
どの操作を行えばいいのかピンポイントでわかるわけないのでシミュレーションすればいいだろうとは思いつつ、どうやればいいのか思いつきませんでした。

解説を見て、つまり1つ目の操作を行うループと2つ目の操作を行うループの二重ループで、全ての組み合わせを単純に全部試せばいいということでした。そう考えると、なんで気づけなかったのかと思ってしまうところです…
2つ目の操作は任意の文字に置き換えられるというのがすごく難しく感じてしまったものの、実装としては単に回文とする上で障害となる（一致しない）件数を数えるだけでしたね。

import java.util.Collections
import kotlin.math.min

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

    var ans = Long.MAX_VALUE
    var aSum = 0L
    repeat(n-1) {
        var bSum = 0L
        if(it != 0) {
            Collections.rotate(s, -1)
            aSum += a
        }

        for(i in 0 until (n / 2)) {
            if(s[i] != s[n - 1 - i]) {
                bSum += b
            }
        }

        ans = min(ans, aSum + bSum)
    }

    println(ans)
}

Collections.rotate() で1つ目の操作を表現しています。2つ目の操作は、先頭と末尾、先頭から2つ目と末尾から2つ目、... を比較できるように添字を調整しています。

あろは1つ目の操作にかかる金額は累計ですが、2つ目の操作にかかる金額は都度リセットという違いがある点や、Intでは収まらない場合がある点などに注意でしょうか。

D - Money in Hand

これはかなり典型的なDPで解ける問題です。DPを勉強してから、本番でDPを使った解法でACしたいとずっと思っていて、ようやくその機会が訪れました。

以前やったこの問題と似たようなものかもしれません。

硬貨の種類を行、合計金額を列とした二次元DP表を使って、その金額に到達するかどうかのフラグを埋めていけばいいです。

上の問題と違うのは、硬貨を使わないことも可能なのでいわば「真下」にも配る必要がある点、硬貨が1枚とは限らないので全部埋める必要がある点です。

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

    val dp = Array(n+1) { BooleanArray(x+1) }
    dp[0][0] = true

    for(i in 0 until n) {
        val (a, b) = abList[i]

        for(j in 0 .. x) {
            if(dp[i][j]) {
                dp[i+1][j] = true

                for(k in 1..b) {
                    val index = j + a * k
                    if(index > x) {
                        break
                    }
                    dp[i+1][index] = true
                }
            }
        }
    }

    if(dp[n][x]) {
        println("Yes")
    } else {
        println("No")
    }
}

配るDPとして実装しています。明らかにそっちのほうが簡単なのですが、最初はなぜか貰うDPで考えてややこしくしてWAになりました。
また、Jumping Takahashiの問題では真下に配る必要がなかったためDP表の最終列を見なくてよかったのですが、今回の問題では見る必要があった点に気付くのが遅れてまたWAです。

解けたのは嬉しかったけど、2ペナはそれなりに痛いですね…

感想

DP解法をACできた嬉しさでトータルでは満足感を覚えましたが、2ペナなのでDPの練習はまだ足りないですね。
それとCがわからなかったのは不覚としか言えないです。任意の文字に置き換えられるというなんとなく大変そうな雰囲気と、出力例1で2番目の操作が先に記載されていることなどに惑わされました。まだまだ甘いですね。

どちらかといえばCが解けなかったことのほうが重いと感じたので、Cの過去問埋めを頑張ったほうがよさそうです。

（執筆時間：34分20秒）

A - Range Swap

B - Cat

C - Rotate and Palindrome

D - Money in Hand

感想

Discussion