AtCoder Beginner Contest 350参加記
AtCoder Beginner Contest 350（Promotion of AtCoderJobs）に参加したので記録を残します。
今回は久しぶりに4完です。しかも緑になっちゃった。びっくりです。
A - Past ABCs
数字部分を取り出して1以上349以下かどうか調べます。ただし316だけは除外。
fun main() {
val s = readln()
val n = s.substring(3, 6).toInt()
if(n != 316 && n in 1..349) {
println("Yes")
} else {
println("No")
}
}
n < 350 として0も含めてしまってWAを出した人が多かったようです。私はたまたまn in 1..349とする方法が最初に思い浮かんだので運が良かったです（？）
B - Dentist Aoki
穴の状態を保持して治療ごとの変化を単純に全て記録します。
Booleanの配列を使って反転していけばよかったのですが、なんかInt配列にしてif文を使っています。きっとツッコミどころ満載の問題文に動揺したせいですね（？？）
fun main() {
val (n, q) = readln().split(" ").map { it.toInt() }
val tList = readln().split(" ").map { it.toInt() }
val teeth = IntArray(n + 1) { 1 }
teeth[0] = 0
for(t in tList) {
if(teeth[t] == 1) {
teeth[t] = 0
} else {
teeth[t] = 1
}
}
println(teeth.count { it == 1 })
}
C - Sort
ちょっと詰まりました。愚直にやろうとすると計算量がどうなるのかちょっとイメージができず。ただ、操作回数ではなく操作自体を出力する必要があるので、やっぱり愚直にやるしかないよなあと思い直しました。
1から順番に、必要な入れ替えを順次していけばよさそう。各数の現在位置を一通り記録して、それをもとに入れ替えを実施、それによって確定した数はそれ以上操作しないようにすれば計算量的にも大丈夫そう。
今回は確定していない値をキューで扱うようにして、キューが空になるまで操作としました。入れ替えを実施しても確定しない数もありますので、確定しない数については入れ替えによる現在位置の変更を反映する必要があります。これを忘れて1ペナを出しました。
例1が綺麗すぎる（入れ替えをしたら両者が確定する）のは気づいていたのになあ…
import java.io.PrintWriter
import java.util.*
import kotlin.collections.ArrayDeque
fun main() {
val n = readln().toInt()
val a = readln().split(" ").map { it.toInt() }
.toMutableList()
val queue = ArrayDeque<Int>()
val pos = IntArray(n + 1)
for(i in 0 until n) {
val index = i + 1
if(a[i] != index) {
queue.add(index)
}
pos[a[i]] = index
}
val ans = mutableListOf<Pair<Int, Int>>()
while (queue.isNotEmpty()) {
val i = queue.removeFirst()
if(a[i-1] != i) {
val old = a[i - 1]
val j = pos[i]
Collections.swap(a, i-1, j-1)
ans.add(i to j)
pos[old] = j
}
}
val out = PrintWriter(System.out)
out.println(ans.size)
ans.forEach {
val (i, j) = it
out.println("$i $j")
}
out.flush()
}
D - New Friends
無向グラフとして考えればいいですね。
グラフを描いてみると、操作後はある頂点から全ての他の頂点へ辺が伸びることがわかりました。これは完全グラフというそうですね。つまり辺を何本足せば完全グラフになるか？ということ。
完全グラフの辺の数は、頂点数を
また、グラフは連結とは限らないです。例3では連結成分が2つあります。連結成分同士がつながることはないので、連結成分ごとに考える必要があります。
それともちろん、連結成分の頂点数が3以上でなければスルーします。
実装としてはUnion-Findを使いました。木を構築して、根の数を求めれば連結成分の個数がわかります。また、根の出現回数を記録すれば連結成分ごとの頂点数もわかります。
なお、既存の辺については調べなくても入力されているわけなのでその分を引けばいいのですが、頂点数が3未満なのでスルーした分の辺の数は引いちゃいけないのでその考慮を入れています。
fun main() {
val (n, m) = readln().split(" ").map { it.toInt() }
val uf = UnionFind(n + 1)
val ab = List(m) {
val (a, b) = readln().split(" ").map { it.toInt() }
uf.union(a, b)
a to b
}
val bucket = IntArray(n + 1)
val set = mutableSetOf<Int>()
for(i in 1..n) {
val root = uf.find(i)
set.add(root)
bucket[root]++
}
var ans = 0L
var diff = 0
for(root in set) {
val count = bucket[root].toLong()
if(count < 3) {
if(count == 2L) {
diff++
}
continue
}
val ideal = count * (count - 1) / 2
ans += ideal
}
println(ans - (m - diff))
}
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]
}
}
}
E - Toward 0
一応見ましたが、ここでいう期待値という言葉の意味がわからず、またググっても残り時間で理解できるとは思えなかったので諦めました。
感想
しばらく4完できてなくて、今回はDの配点が低めだったのでぜひ4完したいなあと思っていました。なんとかそれが果たせたのでよかったですね。Union-Findを本番で使って通せたのも久しぶりだったので嬉しい。しかも入緑できてしまうとは…
Union-Find入緑ですね。ありがたやー
Cでペナを出したのは残念ですが、すぐにリカバリできたのでまあまあ良かったかな。最近はペナを出してもあまり動揺せずに比較的軽傷のうちに対処できることが多い気がします。なんだかんだで力がついてるのかも。
まあ入緑まで行ったのは出来過ぎというか上振れ感がありますので、茶色に戻ってしまってそこから再入緑がなかなかできない、という状況は普通に考えられます。あまりそこで病まないように心の準備をしておきますｗ
心の準備じゃなくて精進をしろと言われれば、それはそうなんですが。
（執筆時間: 40分23秒）
Discussion