AtCoder Beginner Contest 293 A～Dのメモ
AtCoder Beginner Contest 293に参加したので記録を残します。
今回は3完で、Dはコンテスト後に解いたものになります。
A - Swap Odd and Even
やるだけといえばやるだけなのですが、Aにしてはちょっと面倒ですね。
Collections.swap()で楽をしたかったので一旦MutableListに分解してから最後また結合しています。
import java.util.*
fun main() {
val s = readLine()!!.toMutableList()
for(i in 0 until s.size step 2) {
Collections.swap(s, i, i+1)
}
println(s.joinToString(""))
}
B - Call the ID Number
呼ばれてない人を管理するSetを作り、各人が呼ばれたどうかを管理しながら一通り操作をするだけなのですが、なぜか詰まりました。昨日は調子悪かったんだな！そういうことにしよう…
なにげに制約がそれなりにきついので、Setと間違えてListを使うとかするとTLEになるかもしれません。
fun main() {
val n = readLine()!!.toInt()
val a = readLine()!!.split(" ").map { it.toInt() }.toMutableList()
val bucket = BooleanArray(n + 1)
val set = (1..n).toMutableSet()
for(i in 1 .. n) {
if(!bucket[i]) {
bucket[a[i - 1]] = true
set.remove(a[i - 1])
}
}
println(set.size)
println(set.sorted().joinToString(" "))
}
C - Make Takahashi Happy
まず、制約が小さいので全探索だろうなと思いました。
bit全探索でも解けるらしいですが、今回は再帰DFSで解きました。
各マス目が頂点、マス目の移動を辺とするグラフと考えることができます。右または下にしか移動できず、戻るということがないため有向グラフと考えられます。
なので、まずは各マス（頂点）に対して右と下のマス（頂点）へ移動する辺を追加してグラフを生成する処理をします。
グラフを作ったら各頂点の値を記録しながら走査して、
頂点はPairで表現しています。Pairをキーとして使えるように、グラフはMapで表現します。
var graph = mutableMapOf<Pair<Int, Int>, MutableList<Pair<Int, Int>>>()
var a = listOf<List<Int>>()
fun main() {
val (h, w) = readLine()!!.split(" ").map { it.toInt() }
a = listOf(listOf(0)) + List(h) {
listOf(0) + readLine()!!.split(" ").map { it.toInt() }
}
graph = mutableMapOf()
for(i in 0 until h) {
for(j in 0 until w) {
graph.putIfAbsent(i+1 to j+1, mutableListOf())
if(i != h - 1) {
graph[i+1 to j+1]?.add(i+1+ 1 to j+1)
}
if(j != w - 1) {
graph[i+1 to j+1]?.add(i+1 to j+1+1)
}
}
}
dfs(1 to 1, h, w, listOf())
println(ans)
}
var ans = 0
fun dfs(p: Pair<Int, Int>, h: Int, w: Int, list: List<Int>) {
var newList = list + listOf(a[p.first][p.second])
for(node in graph[p]!!) {
if(node == h to w) {
newList = newList + listOf(a[node.first][node.second])
if(newList.size == newList.distinct().size) {
ans++
return
}
}
dfs(node, h, w, newList)
}
}
入力値の受け取りやグラフの生成のところでなんか色々足しているのは1-indexedへの補正のためです。（わかりづらい…）
あと、KotlinのListは不変なので、再帰呼び出しの先で破壊的に変更されることはありません。実行効率は悪いかもしれないですが、可変リストを引き回してバグらせるのも怖かったので…
なお、最初は頂点の値の記録タイミングを間違えるという初歩的ミスでWAを出しました…
Bで時間を食った後のWAなので焦りましたが、まあ1ペナで済んでよかったのかな。
D - Tying Rope
グラフかな。連結成分にサイクル検出……Union-Findや！！
ってところまでは発想したのですが、色とかどうやって扱ったらいいんだろうと悩む。今思えばロープの各端のそれぞれを頂点とみなして、被ることがない番号を振って、ロープの両端は事前に連結させておけばよかったのですが、なんでコンテスト中に気づけなかったんだろうなあという感じ。
つまりサイクルの件数が
実装としては、色Rの端の頂点番号はそのまま、色Bの場合は
それで、同じロープの両端は入力値を受け取る前に連結させておきます。
入力値を受け取るところでは、サイクル検出をしつつ連結させていきます。Union-Findを使うと2頂点が連結かどうかを高速に判定できます。これから連結させようとしている2頂点が既に連結であれば、それを追加で連結させるとサイクルが発生するということなので、それを利用してサイクルの件数を数えることができます。
（Union-Findを使ったサイクル検出の一般的な方法みたいです）
全部終わったら、連結成分の数を数えます。Union-Findでは頂点番号を入力するとそれが属する連結成分の根を取得することができます。なので全ての頂点番号に対する根を取得して、それが何種類あるかが連結成分の個数と一致します。
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val diff = n
val uf = UnionFind(n + diff + 1)
for(i in 1..n) {
uf.union(i, i + diff)
}
var x = 0
repeat(m) {
val (a, b, c, d) = readLine()!!.split(" ")
val aa =if(b == "R") {
a.toInt()
} else {
a.toInt() + diff
}
val cc = if(d == "R") {
c.toInt()
} else {
c.toInt() + diff
}
if(uf.isSame(aa, cc)) {
x++
}
uf.union(aa, cc)
}
val num = (1..n + diff).map { uf.find(it) }.distinct().size
println("$x ${num - x}")
}
private class UnionFind(n: Int){
private val roots = IntArray(n){ it }
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]
}
}
}
結果としては概ねUnion-Find貼るだけ…！
解説は見ずに解きましたが、まあTwitterでヒントはがっつり見てからの話なので自力とはいえないですね。ただ直接的には解法を見ていないので、解けたかもしれない問題を落としたという認識になります。
追記
もっと簡単な方法をTwitterで見ました。ロープ自体を一つの頂点とみなすことができます。つまりRとかBとか無視して単純に番号だけで扱います。
fun main() {
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
val uf = UnionFind(n + 1)
var x = 0
repeat(m) {
val (a, b, c, d) = readLine()!!.split(" ")
val aa = a.toInt()
val cc = c.toInt()
if(uf.isSame(aa, cc)) {
x++
}
uf.union(aa, cc)
}
val num = (1..n).map { uf.find(it) }.distinct().size
println("$x ${num - x}")
}
private class UnionFind(n: Int){
private val roots = IntArray(n){ it }
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]
}
}
}
これは気づかなかった…
感想
気持ち的には大敗だったのですが、レート的にはなぜか-1で済みました。一応Cは解けたのと、Dは悔しいけど本番でUnion-Findを発想する経験まではできたので、トータルでは儲けです。
Union-Find貼るだけとはいっても、Union-Findの概要とサイクル検出の方法は知らないと発想すらできないので、一応以前ならできなかったことができたとは言えますｗ
ゆっくりだけど前には進んでいるので、これからもほどほどに頑張ります。
（執筆時間: 44分15秒）
Discussion