AtCoder Beginner Contest 292 A～Dのメモ
AtCoder Beginner Contest 292に参加したので記録を残します。
今回は4完です。
A - CAPS LOCK
大文字に変換するだけなので、そういうメソッドがある言語なら一発です。
fun main() {
val s = readLine()!!
println(s.toUpperCase())
}
個人的にはたぶん今までで最速の提出でした。（23秒）
いつもなんだかんだで1分くらいかかってるんですよね…
今回は問題文の読解がほぼいらなかったのと、入力がほぼIDEAによる補完だけで終わったのと、さすがにWAはないだろうと思って入力例1しか試さなかったので速くなりました。
（入力値の受け取り部分はLive Templateとして登録しています）
B - Yellow and Red Card
イエローカードの場合はペナルティ1、レッドカードの場合はペナルティ2を足すと考えました。選手ごとにペナルティを管理して、2以上になっていたら退場という判定です。
コンテスト中はちゃんと考えてなかったですが、イエローカードを1回、レッドカードを1回提示されてペナルティが3もあり得そうですね。それでも問題ない実装にしていましたが。
難しくはないけど実装が若干面倒でしたね。
fun main() {
val (n, q) = readLine()!!.split(" ").map { it.toInt() }
val event = Array(q) {
readLine()!!.split(" ").map { it.toInt() }
}
val bucket = IntArray(n+1)
for(e in event) {
val (t, x) = e
if(t == 1) {
bucket[x]++
} else if(t == 2) {
bucket[x] += 2
} else if(t == 3) {
if(bucket[x] >= 2) {
println("Yes")
} else {
println("No")
}
}
}
}
C - Four Variables
ちょっと自分には難しい気がすると思って一旦飛ばしましたが、Dが解けたので戻ってきて解きました。（一応解けた）
たとえば入力例1で挙がっている4については、
1 + 3 2 + 2 3 + 1
の3通りです。
最大値でも
「何か」+「何か」ですが、その「何か」は2つの数の積です。その2つの数の組み合わせのパターン数を計算で求められればよさそうですが、結果としてはそのパターン数はその数の約数の個数に等しそうだとわかりました。（いくつか試してみて、帰納的に…）
上記の4を分解した例だと、要素が1か素数だけでわかりづらいので、12とかで考えてみます。
12を2の数の積で作る組み合わせは
1 × 12 2 × 6 3 × 4 4 × 3 6 × 2 12 × 1
の6通りです。これは約数の数に等しいです。
約数の個数を求めるのが遅かったら意味がないので、速そうな実装をネットから拾ってきました。
答えは64bit整数型にする必要があります。
fun main() {
val n = readLine()!!.toInt()
var ans = 0L
for(i in 1 until n) {
val a = i
val b = n - i
ans += divisors(a)* divisors(b)
}
println(ans)
}
fun divisors(n: Int): Int {
val lower = mutableSetOf<Int>()
val upper = mutableSetOf<Int>()
var i = 1
while(i * i <= n) {
if(n % i == 0) {
lower.add(i)
if(i != n / i) {
upper.add(n / i)
}
}
i++
}
return lower.size + upper.size
}
D - Unicyclic Components
グラフですね。やり方としては、頂点と辺の数を数え上げて比較という愚直な方法になりました。
わりと似たような問題を解いてきたので解けそうと思いました。ただ、今までは多重辺や自己ループのない単純グラフばかり扱っていましたが、この問題では単純グラフとは書いていないので、それらがあり得るということです。
実際、入力例1は以下のようなグラフとなっています。
ただ、連結成分ごとに探索するというのは何度かやっているので、過去の実装を流用して少し直せばいけそうな気がしました。
実際、最近やったこの問題のDFS実装を拾ってきて修正して対応しました。
最初の提出コードは以下です。
全ての連結成分を探索するので全ての頂点からの探索開始を試行する、しかし頂点に訪問済ならそれが属する連結成分は探索済なのでスルー、未知の連結成分なら探索して頂点と辺の数を数える、不一致ならその時点でNo、最後までNoにならなかったらYes、です。
@OptIn(ExperimentalStdlibApi::class)
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 stack = ArrayDeque<Int>()
val seen = BooleanArray(n + 1)
val map = mutableMapOf<Int, MutableSet<Int>>()
for(i in 1..n) {
if(seen[i]) {
continue
}
stack.add(i)
seen[i] = true
val nodes = mutableSetOf<Int>()
var edgeCount = 0
while (stack.isNotEmpty()) {
val v = stack.removeLast()
nodes.add(v)
for(node in graph[v]) {
if(node in map.getOrDefault(v, mutableSetOf())) {
continue
}
map.putIfAbsent(node, mutableSetOf())
map[node]?.add(v)
edgeCount++
if(seen[node]) {
continue
}
seen[node] = true
stack.add(node)
}
}
if(nodes.size != edgeCount) {
println("No")
return
}
}
println("Yes")
}
多重辺と自己ループは特に考慮しなくても動いた気がするのでそのまま提出ｗ
しかしダメ。
しかしWAが3件だけなので、基本的な考え方は合っていて、コーナーケースに引っかかっているという感じですね。
どういうケースが問題なのかなと考えました。重複して数えてしまっているというのはバグとしてはあり得るが、頂点の数のカウントはSetでズルしている（？）のでたぶん合っている、辺の数のカウントは怪しいけど、そこで間違っているならもっとたくさんWAが出る気がする、のでカウント漏れのほうが怪しいと思いました。
結果的には、頂点が1つしかない連結成分に自己ループが2以上あった場合が漏れていました。
私のごちゃごちゃした実装が原因なのですが、そのようなケースは途中で探索を切り上げてしまって辺の数が1つと判定してしまっていました。
ちょっとそれをうまく修正しようとすると他のバグが出そうなので頭を抱えましたが、そのような場合はその頂点から伸びる辺は全て同じなわけなので、探索せずとも判定できると気づきました。
最終的な提出コードは以下です。
@OptIn(ExperimentalStdlibApi::class)
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 stack = ArrayDeque<Int>()
val seen = BooleanArray(n + 1)
val map = mutableMapOf<Int, MutableSet<Int>>()
for(i in 1..n) {
if(seen[i]) {
continue
}
stack.add(i)
seen[i] = true
val nodes = mutableSetOf<Int>()
var edgeCount = 0
while (stack.isNotEmpty()) {
val v = stack.removeLast()
nodes.add(v)
// ※ここを追加
if(graph[v].size != 1 && graph[v].distinct().size == 1 && graph[v].size != 2) {
println("No")
return
}
for(node in graph[v]) {
if(node in map.getOrDefault(v, mutableSetOf())) {
continue
}
map.putIfAbsent(node, mutableSetOf())
map[node]?.add(v)
edgeCount++
if(seen[node]) {
continue
}
seen[node] = true
stack.add(node)
}
}
if(nodes.size != edgeCount) {
println("No")
return
}
}
println("Yes")
}
追加箇所にコメントを入れました。つまり問題のケースだとその頂点から伸びる辺のリストがたとえば [1, 1, 1, 1] のようになっています。無向グラフということで行き帰りの両方を追加するので、自己ループの数 × 2個が保存されます。
なので[1, 1] のように保存されているのが2つの場合だけOKと考えて、その判定を入れました。
すごく…無理やりだけどまあ通ったのでヨシ！
（今思えば、辺の行き先がvと同じかどうかを見たほうがよかったような気がする…）
感想
Dは以前解いた問題の実装を流用できたので楽ができましたね。過去そういう問題を解いていなかったら解けなかったはずなので、やはり問題を色々解いてみるのが正義ですね…
C問題が解けたのは嬉しかったです。ネットから拾ってきたものに依存するなど脆弱な点はありますが、
まあ数学というか算数レベルなのかもしれないけど、たぶん以前の自分なら思いつきもしなかったです。数弱だと、数とは分解可能なものであるという発想自体がなかったりするもので。
とりあえず、まだ満足できるような水準では全くないにせよ、進歩はありそうということでよかったです。
しかしDはパッチを当てるような実装で通したのでちょっと怪しかったですね。無向グラフでのサイクル判定のためのごちゃごちゃしたコードを改善したほうがいいかも…
（執筆時間: 1時間15分17秒）
Discussion