AtCoder Beginner Contest 288 A～Dのメモ
Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288）に参加したので記録を残します。
A - Many A+B Problems
入力値を足して出力するだけです。一旦変数に格納した後に再度ループするとか無駄なことをついやってしまっています…
fun main() {
val n = readLine()!!.toInt()
val ab = List(n) {
val (a, b) = readLine()!!.split(" ").map { it.toLong() }
a to b
}
for(i in 0 until n) {
println(ab[i].first + ab[i].second)
}
}
B - Qualification Contest
ちゃんと問題文を読んでなくて、全部を辞書順に出そうとしてしまいましたが、よく見たら出力するのは上位K人分だけでした。
上位の人から順に入力されるので、実装としては入力のうち前からK個分だけ使ってそれを昇順ソートとなります。
fun main() {
val (n, k) = readLine()!!.split(" ").map { it.toInt() }
val s = List(n) {
readLine()!!
}
.take(k)
.sorted()
s.forEach {
println(it)
}
}
これも変数に入れずそのまま続けてforEachを呼べばよかったのにねぇ。
C - Don’t be cycle
最近似たような問題が続きますね。
要するにサイクルを検出してその件数を数えればいいんだろうと思いました。
サイクルを見つけたらそれ以上は辿らず、件数をカウントアップ。それで全体を探索するだけでいいだろうと。
下手な絵ですが例1はこんなグラフです。サイクルが2箇所あります。
出力例1の記載だと、以下の通り2箇所を消すことでサイクルをなくせます。
なのでサイクル1つあたり1つの辺を削除すればいい、つまりサイクルの件数が答えとなりそう。
サイクルの検出は、走査済のフラグ seen で管理して、探索済のところを再度探索しようとしたらサイクル検出。
ただし、無向グラフなので親に再訪問しないように考慮は必要。
どこから探索を始めればいいのかわからないけど、まあ1からでいいやろ（適当）
先週も似たような問題を解いたし、よゆーよゆー
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val graph = Array(n + 1) { mutableListOf<Int>() }
repeat(m) {
val (a, b) = readLine()!!.split(" ").map { it.toInt() }
graph[a].add(b)
graph[b].add(a)
}
val queue = java.util.ArrayDeque<Int>()
queue.add(1)
val seen = BooleanArray(n + 1)
seen[1] = true
val map = mutableMapOf<Int, MutableSet<Int>>()
var count = 0
while (queue.isNotEmpty()) {
val v = queue.poll()
for(node in graph[v]) {
if(node in map.getOrDefault(v, mutableSetOf())) {
continue
}
map.putIfAbsent(node, mutableSetOf())
map[node]?.add(v)
if(seen[node]) {
count++
continue
}
seen[node] = true
queue.add(node)
}
}
println(count)
}
が、ダメ…！
しばらく椅子を温めたり、無意味な修正を投げてみて2ペナ目をもらったりしました。
少し経ってハッと気づいたのが、これって連結とは限らないんじゃない？ということ。
たとえばこういうグラフかもしれない。
この場合、1からはどこにも辿れないので、探索開始位置が1固定だとサイクルを見つけられず、答えは0と出力してしまいます。
しかし実際にはサイクルがあるのでWAです。
じゃあどうすればいいかというと、探索の開始位置を1からNまで全部試せばいいのではと思いました。以前連結成分の個数を数える問題があり、それでも同じようなことをしていたので。
未知の連結成分だった場合だけ探索すればいいので無駄な探索は発生せず、計算量としてもたぶん大丈夫だろうと…
直したのがこちら。
（BFSだったのがDFSに変わっているのは試してみただけで、実際には意味はありません）
@OptIn(ExperimentalStdlibApi::class)
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val graph = Array(n + 1) { mutableListOf<Int>() }
repeat(m) {
val (a, b) = readLine()!!.split(" ").map { it.toInt() }
graph[a].add(b)
graph[b].add(a)
}
val stack = ArrayDeque<Int>()
val seen = BooleanArray(n + 1)
val map = mutableMapOf<Int, MutableSet<Int>>()
var count = 0
for(i in 1..n) {
if(seen[i]) {
continue
} else {
stack.add(i)
seen[i] = true
}
while (stack.isNotEmpty()) {
val v = stack.removeLast()
for(node in graph[v]) {
if(node in map.getOrDefault(v, mutableSetOf())) {
continue
}
map.putIfAbsent(node, mutableSetOf())
map[node]?.add(v)
if(seen[node]) {
count++
continue
}
seen[node] = true
stack.add(node)
}
}
}
println(count)
}
AC！しかし実行時間がギリギリです…
コンテスト後に見直してみましたが、なぜこんなにギリギリになってしまうのかはよくわからず。
ちなみに、Union-Findを使えば一発みたいな話も見ました。先週もそういう話だったような…
Union-Findについてはまだよくわかっていないのですが、KotlinによるUnion-Findの実装を適当に拾って手を加えて、この問題をUnion-Findで解いている提出コードをもとにささっと書いてみたのがこちら。
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val uf = UnionFind(n + 1)
var count = 0
repeat(m) {
val (a, b) = readLine()!!.split(" ").map { it.toInt() }
if(uf.isSame(a, b)) {
count++
}
uf.union(a, b)
}
println(count)
}
private class UnionFind(n: Int){
private val roots = IntArray(n){idx -> idx}
private val ranks = IntArray(n){ 1 }
fun find(i: Int): Int{
if(roots[i] != i){
roots[i] = find(roots[i])
}
return roots[i]
}
fun isSame(x: Int, y: Int): Boolean {
return find(x) == find(y)
}
fun union(x: Int, y: Int){
val rootX = find(x)
val rootY = find(y)
if(ranks[rootX] > ranks[rootY]){
roots[rootY] = rootX
++ranks[rootX]
}else{
roots[rootX] = rootY
++ranks[rootY]
}
}
}
これでバッチリACでした。
ほんとにUnion-Findを貼るだけですね…
こんなことなら後回しにせずに早く勉強しておけばよかったなあ。
追記
Uinon-Findの実装で一部誤りがあると指摘をいただきました。
private class UnionFind(n: Int){
private val roots = IntArray(n){idx -> idx}
private val ranks = IntArray(n){ 1 }
fun find(i: Int): Int{
if(roots[i] != i){
roots[i] = find(roots[i])
}
return roots[i]
}
fun isSame(x: Int, y: Int): Boolean {
return find(x) == find(y)
}
fun union(x: Int, y: Int){
val rootX = find(x)
val rootY = find(y)
if(rootX == rootY) { // 追加
return // 追加
} // 追加
if(ranks[rootX] > ranks[rootY]){
roots[rootY] = rootX
++ranks[rootX]
}else{
roots[rootX] = rootY
++ranks[rootY]
}
}
}
結合操作の際、根が同じだった場合は操作しないのが正しかったです。計算量削減のための仕組みがうまく動かなくなります。
（どちらにせよ動くっちゃ動くので、誤りのコードでACしたのはテストケースが弱いとかではないです）
D - Range Add Query
Dはサッパリでした。結果的には青diffだったので解けるわけなかったのですが。
解説もよくわかりませんが、一応コンテスト中に考えて問題文の意味くらいは理解したので、メモは残しておきます。
問題文の意味を理解するのにも少し時間がかかりましたが、要するに数列Aの連続部分列が指定されるので、その部分数列の要素を全て0にすることができるかどうかということですね。
- 連続部分列は、数列Aの何番目から何番目か、という形式で指定される
- 0にするために実行することができるのは、その連続部分列の中の特定の範囲の要素全てに対して同じ数を足すこと
- 範囲の長さはKで固定で、連続している必要がある
- 足す数は何でもありで、負の数でもいい。ただし同じ数でないといけない
- 操作は何度でも実行できるし、1度も実行しなくてもいい
それで、判定が必要なのは1件だけでなく、連続部分列はQ個指定されるので、その全てに対して判定して答えを出力します。
Qの制約が大きいので、全体で
全探索は制約的にも許されませんが、そもそも足す数（c）に対する制約が何もないので、全探索というのがそもそも不可能です。そういう発想だと、どのような場合に全て0にすることができないと言えるのか全然わかりませんし。
連続部分列の要素1つ1つをチェックすることすら許されない制約なので、事前に何か累積和的なデータ構造を作っておいて計算で求めるのだろうなとは思いました。具体的には何なのか全然わかりませんが。
（偶然ですが、実際累積和を使うのが想定解だったようです。単純な累積和でなさそうですが）
0に限らず連続部分列の数字が全て揃えばいいんだよねとか、Kの制約は妙に小さいねとかは思いましたが、それ以上のことはわからず。
青diffを頑張って解説ACする気にはなれないので、今回はここまで…
感想
Dは解けるわけなかったのでいいのですが、Cの2ペナは残念でしたね。単純無向グラフは連結とは限らないって、最近も見たことなのに見落としたのは不覚です。
あと今回使ってみたUnion-Findの実装はとりあえずライブラリとして残しておきます。原理はまだ理解していないですが、とりあえず使い方がわかれば役に立つかもしれないので。
グラフを集中的に練習しようかなーって先週書いたのですが、実際にはできていなかったので、来週からはやります…
ここ最近グラフばっかりなので、反動でしばらく出なくなる可能性もありますが、長期的に見れば出続けるはずなのでバッチリ仕上げておきたいですね。
（執筆時間：1時間16分47秒）
Discussion