👋

AtCoder Beginner Contest 289 A~Dのメモ

2023/02/12に公開

Sky株式会社プログラミングコンテスト2023(AtCoder Beginner Contest 289)に参加したので記録を残します。
https://atcoder.jp/contests/abc289

今回はノーペナ4完なのでそれなりです。

A - flip

問題文の通りやるだけです。最初replaceしようかと思ったけど面倒だったのでmapを使いました。
(連想配列ではなく)

fun main() {
    val s = readLine()!!
    println(s.map { if(it == '1') '0' else '1' }.joinToString(""))
}

B - レ

レ点ですか…たぶん昔習ったけど何も覚えてない。

無向グラフとか、問題文がとてもB問題とは思えないですね…焦りました。
とはいえ実際にはB問題なので、グラフとして扱わなくても簡単に解く方法があるんだろうなと思いつつ、ちょっと焦った頭では思いつくか自信なかったので結局グラフとして問題文の通り実装しました。

無向グラフを作って、まだ読んでない数字を set で管理して、 set の最小値から探索を開始、探索の中で見つかった要素を一時リストに詰めて、連結成分の中で探索が終わったら見つかったリストを降順ソートして全体の結果リストに入れる、を繰り返しました。

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

    val s = readLine()!!
    if(s.isEmpty()) {
        println((1..n).joinToString(" "))
        return
    }


    val aList = s.split(" ").map { it.toInt() }

    val graph = Array(n+1) { mutableListOf<Int>() }

    for(a in aList) {
        graph[a].add(a+1)
        graph[a+1].add(a)
    }

    val set = (1..n).toMutableSet()

    val ans = mutableListOf<Int>()
    while(set.isNotEmpty()) {
        val min = set.min()!!
        set.remove(min)

        val queue = java.util.ArrayDeque<Int>()
        queue.add(min)

        val seen = mutableSetOf<Int>()

        val list = mutableListOf<Int>()
        while (queue.isNotEmpty()) {
            val v = queue.removeFirst()

            seen.add(v)
            list.add(v)

            for(node in graph[v]) {
                if(node in seen) {
                    continue
                }

                list.add(node)
                seen.add(node)
                queue.add(node)
            }
        }
        ans.addAll(list.sortedDescending())
        set.removeAll(list.toSet())
    }

    println(ans.distinct().joinToString(" "))
}

明らかにいらない変数があったり、計算量は全く考えてなかったり、そもそも2重に同じ要素を追加して最後に重複排除して出力しているとかグッダグダですね…

これで15分くらい使ってしまいました。WAが出なくてよかった…

C - Coverage

こういう何個選ぶのか決まっていなくて、かつ制約が小さいのはbit全探索で解ける典型的な問題ですね。
わざわざ2^M−1通りあるなんて書いてあるし、かなり意図して典型問題として作った感じですね。
(全パターンだと2^M通りですが、一つも選ばないのは不可なのでその分-1)

しかしbit全探索はまだ苦手です。考え方としてはシンプルで、どの集合を選択するのか決めた後に、1からNまでの数の全てが選択済みの集合の中のどれかに入っていることを確認するだけなのですが、実装がごちゃごちゃして混乱します。
こういう問題ももっと練習して早く解けるようになりたいですね。

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

    val cs = List(m) {
        val c = readLine()!!.toInt()
        val a = readLine()!!.split(" ").map { it.toInt() }.toSet()

        c to a
    }

    var ans = 0
    for(bit in 1 until (1 shl m)) {
        var flg1 = true
        for(x in 1..n) {
            var flg2 = false
            for(i in 0 until m) {
                if(bit and (1 shl i) != 0) {
                    if(x in cs[i].second) {
                        flg2 = true
                        break
                    }
                }
            }
            if(!flg2) {
                flg1 = false
                break
            }
        }
        if(flg1) {
            ans++
        }
    }
    println(ans)
}

flg1 とか flg2 とか変数名がひどいですね…
flg1 はその集合の選び方を答えとしてカウントするかどうかのフラグ、 flg2x を探索する際、選択した集合のうち一つでも含まれるものがあったらtrueになります。
x の中で、 flg2 が一度もtrueにならないことがあったら flg1 がfalseになってその選び方はNG、という感じです。

D - Step Up Robot

いかにもDPという感じがしました。取り組んでみたらまさにDPでした。しかも1次元DP。
以前解いたこの問題と非常に似ていました。
https://zenn.dev/dhirabayashi/articles/974ead4edbab71

1次元のDP表(Boolean配列)を作り、配列のi番目がi段目に到達可能かどうかのフラグです。
Xに到達可能かどうかだけが重要なので、配列は x + 1 の大きさにします。0-indexedなので+1が要ります。あと0段目にいる状態を表現したいので。
最初は0段目にいるので dp[0]はtrueで初期化、それ以外はfalseで初期化です。
DP表をdp[0]から順に見ていって、そこが到達可能でかつモチがない段であれば、A_1 ,A_2,…,A_Nを足した位置を全て到達可能としてtrueにします。(範囲外にならないように注意)
それを最後まで繰り返して、最終的に dp[x] が到達可能になっているかどうかで答えを出力すればいいです。

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

    val dp = BooleanArray(x + 1)
    dp[0] = true

    for(i in 0 until x) {
        if(i in b) {
            continue
        }

        if(!dp[i]) {
            continue
        }

        for(j in a.indices) {
            if(i + a[j] <= x) {
                dp[i + a[j]] = true
            }
        }
    }

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

モチがある段に行ったらそこで止まってしまうけど、一応行けないわけではないのでそういう実装にしましたが、よく見たら X がモチのある段になることはない制約になっているので、モチがある段には行けないと考えても結果的に問題はないのかもしれません。

かなり前のC問題の類題ということで、一般的なD問題レベルではないかなという気はします。

E - Swap Places

これもグラフですね。問題文の意味はわかるけど、高橋君の移動先の色と青木君の移動先の色が異なる必要があるというのをどうやって実現したらいいのかわからず。
別途解説ACしてみます。

感想

Bはともかく、CやDは典型で、以前似たような問題をやったことがあるということもあって解けたのでよかったです。2度目の緑パフォが出て嬉しかった。
まあちょっと捻った問題が出てくると途端に解けなくなるので、問題が簡単であったことに救われた形ではありますが、まあ簡単な問題ならノーペナで通せる程度の力はあるということで一応喜んでおきます。
なんというか私は、まあ、いかにも茶色だな、うん。

(執筆時間:49分01秒)

Discussion