AtCoder Beginner Contest 289 A～Dのメモ
Ｓｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 289）に参加したので記録を残します。
今回はノーペナ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全探索で解ける典型的な問題ですね。
わざわざ
（全パターンだと
しかしbit全探索はまだ苦手です。考え方としてはシンプルで、どの集合を選択するのか決めた後に、1から
こういう問題ももっと練習して早く解けるようになりたいですね。
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 はその集合の選び方を答えとしてカウントするかどうかのフラグ、 flg2 は x を探索する際、選択した集合のうち一つでも含まれるものがあったらtrueになります。
x の中で、 flg2 が一度もtrueにならないことがあったら flg1 がfalseになってその選び方はNG、という感じです。
D - Step Up Robot
いかにもDPという感じがしました。取り組んでみたらまさにDPでした。しかも1次元DP。
以前解いたこの問題と非常に似ていました。
1次元のDP表（Boolean配列）を作り、配列の
x + 1 の大きさにします。0-indexedなので+1が要ります。あと0段目にいる状態を表現したいので。
最初は0段目にいるので dp[0]はtrueで初期化、それ以外はfalseで初期化です。
DP表をdp[0]から順に見ていって、そこが到達可能でかつモチがない段であれば、
それを最後まで繰り返して、最終的に 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")
}
}
モチがある段に行ったらそこで止まってしまうけど、一応行けないわけではないのでそういう実装にしましたが、よく見たら
かなり前のC問題の類題ということで、一般的なD問題レベルではないかなという気はします。
E - Swap Places
これもグラフですね。問題文の意味はわかるけど、高橋君の移動先の色と青木君の移動先の色が異なる必要があるというのをどうやって実現したらいいのかわからず。
別途解説ACしてみます。
感想
Bはともかく、CやDは典型で、以前似たような問題をやったことがあるということもあって解けたのでよかったです。2度目の緑パフォが出て嬉しかった。
まあちょっと捻った問題が出てくると途端に解けなくなるので、問題が簡単であったことに救われた形ではありますが、まあ簡単な問題ならノーペナで通せる程度の力はあるということで一応喜んでおきます。
なんというか私は、まあ、いかにも茶色だな、うん。
（執筆時間：49分01秒）
Discussion