AtCoder Beginner Contest 287 A～Cのメモ
ユニークビジョンプログラミングコンテスト2023 新春 (AtCoder Beginner Contest 287)に参加したので記録を残します。
今回はなかなか残念な結果でした。
A - Majority
"Against"の人数よりも"For"の人数のほうが多いかどうかを判定してもいいのですが、全体の人数がわかっているので"For"の人数だけ数えればOKです。
両方数えても制約的には全然問題ないですけども。
fun main() {
val n = readLine()!!.toInt()
val sList = List(n) {
readLine()!!
}
if(sList.filter { it.equals("For") }.size > n / 2) {
println("Yes")
} else {
println("No")
}
}
B - Postal Card
まあこれもやるだけではあります。2重ループでチェックするだけ。
以下の実装だとリスト操作のメソッドを使っているので明示的にはループは書いてないですが、内部的にループしています。
countはラムダ式で渡した条件に合致する要素の件数を取得するメソッド、anyはラムダ式で渡した条件に合致する要素が1件でもあったらtrueを返すメソッドです。
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val sList = List(n) {
readLine()!!
}
val tList = List(m) {
readLine()!!
}
val ans = sList.count { s -> tList.any { t -> s.substring(3, 6) == t } }
println(ans)
}
C - Path Graph?
入力されたグラフがパスグラフかどうかを判定する問題です。シンプルなのですが、なんかドハマりしました……
パスグラフとは、わかりやすく言えば1直線に繋がるグラフですね。全て繋がっていて、かつ余計な辺は存在しないと。
出力例1の下に描かれているのが説明的ですね。
入力される単純無向グラフですが、自己ループや多重辺はないけどサイクルはあり得るし、連結成分が2つ以上もあり得ます。
（出力例2、3からもわかりますが）
Union-Findで一発みたいな情報を見ましたがあいにく未履修で、BFSとかで探索してチェックできるはずと思ったのでその方向で考えました。
とりあえず、連結成分が1つとは限らないので1からNまで全て探索可能かを判定する必要がある、かつサイクルがないかを判定する必要がある、かつ次数が2以下かどうかを判定する必要がある、ということになります。
サイクルがないかどうかは探索済の頂点を再度探索していないかどうかで見ることができますが、無向グラフなので元のほうに戻らないようにする考慮は必要になります。（それでちょっと悩んだ）
一応整理して投げたのがこちら。（通りません）
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val graph = Array(n + 1) { mutableListOf<Int>() }
repeat(m) {
val (u, v) = readLine()!!.split(" ").map { it.toInt() }
graph[u].add(v)
graph[v].add(u)
}
val queue = java.util.ArrayDeque<Int>()
queue.add(1)
val seen = mutableSetOf<Int>()
seen.add(1)
val map = mutableMapOf<Int, MutableSet<Int>>()
while (queue.isNotEmpty()) {
val v = queue.poll()
var count = 0
for(node in graph[v]) {
if(node in map.getOrDefault(v, mutableSetOf())) {
continue
}
map.putIfAbsent(node, mutableSetOf())
map[node]?.add(v)
count++
if(count > 1) {
println("No")
return
}
if(node in seen) {
println("No")
return
}
seen.add(node)
queue.add(node)
}
}
if(seen.size == n) {
println("Yes")
} else {
println("No")
}
}
1からNまで全て探索可能かどうかは、探索済の頂点数がNかどうかで最後に判定しています。
サイクルがないかどうかは、探索済の頂点を再度訪問していないかどうかで見ています。（ただし探索元に戻るケースだけは除外）
あとは次数が2以下かどうかの判定なんですが、これが間違っていました。2より大きかったらNGなのに1より大きかったらNGという条件にしています…
しかし、探索元に戻るケースについては件数としてカウントしていないことにより、これでもサンプルは通ってしまいました。
これで通らないケースですが、たとえば以下のようなグラフです。
1から探索を開始するので、1から見ると4と3の2箇所へ探索するので上記コードだとNoが出力されます。しかし、実際にはパスグラフなのでWAです。
上記のケースにコンテスト終了直前に気づき、あわあわして次数のチェック箇所をコメントアウトしたコードを投げてみました。そしたらなんと通ってしまいました。
import kotlin.math.max
import kotlin.math.min
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val graph = Array(n + 1) { mutableListOf<Int>() }
repeat(m) {
val (u, v) = readLine()!!.split(" ").map { it.toInt() }
graph[u].add(v)
graph[v].add(u)
}
if(n - 1 != m) {
println("No")
return
}
val queue = java.util.ArrayDeque<Int>()
queue.add(1)
val seen = mutableSetOf<Int>()
seen.add(1)
val set = mutableSetOf<Pair<Int, Int>>()
while (queue.isNotEmpty()) {
val v = queue.poll()
var count = 0
for(node in graph[v]) {
if(min(node, v) to max(node, v) in set) {
continue
}
set.add(min(node, v) to max(node, v))
count++
if(count > 1) {
// println("No")
// return
}
if(node in seen) {
println("No")
return
}
seen.add(node)
queue.add(node)
}
}
if(seen.size == n) {
println("Yes")
} else {
println("No")
}
}
しかしこれは完全に嘘解法で、以下のような明らかにパスグラフでないグラフでもYesになってしまいます。
ということでAfterContestのケースが追加され、当然落ちました。
このままだと当然良くないので、AfterContestのケースも含めてちゃんと通るコードに修正したい。
AfterContestのケースで落ちた理由は考えるまでもなく、次数をチェックしていないからです。
なので正しくカウントできるようにしました。
まあ上で半分答えは書いているのですが、次数が1ではなく2を超えたらNGという条件にして、かつ探索元へ戻らないように制御すべきケースでも次数としてはカウントするようにすることで通りました。
（なんか残骸もありますが気にしないでください…）
次数についてちゃんと考えると、両端の頂点の次数は1で、それ以外は2になるはずなんですよね。
両端の頂点の次数が1かどうかはチェックしていないですが、両端の次数が2だったらサイクルがあるってことですし、それは別の条件で弾いているので問題ないはずと。
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val graph = Array(n + 1) { mutableListOf<Int>() }
repeat(m) {
val (u, v) = readLine()!!.split(" ").map { it.toInt() }
graph[u].add(v)
graph[v].add(u)
}
if(n - 1 != m) {
println("No")
return
}
val queue = java.util.ArrayDeque<Int>()
queue.add(1)
val seen = mutableSetOf<Int>()
seen.add(1)
val map = mutableMapOf<Int, MutableSet<Int>>()
val degreeMap = mutableMapOf<Int, Int>()
while (queue.isNotEmpty()) {
val v = queue.poll()
var count = 0
for(node in graph[v]) {
count++
if(node in map.getOrDefault(v, mutableSetOf())) {
continue
}
map.putIfAbsent(node, mutableSetOf())
map[node]?.add(v)
if(node in seen) {
println("No")
return
}
seen.add(node)
queue.add(node)
}
if(count > 2) {
println("No")
return
}
}
if(seen.size == n) {
println("Yes")
} else {
println("No")
}
}
なので最終的なアルゴリズムとしては、1を始点としてBFSで探索、次数が3以上の頂点を見つけたらNo、探索元に戻らないように考慮しつつ、探索済の頂点に再度訪れることがあればNo、探索が終わった後に探索済頂点の数がNと一致すればYes、そうでなければNo、となります。
感想
力不足としか言えないですね…
グラフのコード上での扱い方について、テンプレとして記憶しているだけでちゃんと理解はしていないと感じました。
パスグラフの場合、両端の頂点以外の次数は2であるなんて画像を見れば一発でわかるのに、コードに落とし込む際になんか認識がバグって変なコードになっていました。
グラフはもっともっと練習が必要ですね。まあ練習が必要なのは全部ですが、ABCでは体感的にグラフは明らかに頻出なので、グラフを集中的に練習するのはアリかもと思いました。
あとは、D問題はコンテスト中には着手できず。パッと見た感じだとなんか面白そうな問題だったので残念です。コンテスト後でも解けるといえばそうなんですが、やはりコンテスト中の緊張感の中で解きたかったな。
まあそれが叶わなかったのは力不足の結果でしかないので、どのように考えてももっと精進しろという結論しか出ませんｗ
（執筆時間：55分30秒）
Discussion