AtCoder Beginner Contest 284 A～Eのメモ
AtCoder Beginner Contest 284（ABC284）に参加したので記録を残します。
AからDまではコンテスト中に解いたもの、Eはコンテスト終了の5分後くらいに通ったものです（白目）
A - Sequence of Strings
配列を逆順で出力するだけです。reversed()で逆順にしています。
fun main() {
val n = readLine()!!.toInt()
val s = List(n) {
readLine()!!
}
s.reversed().forEach {
println(it)
}
}
B - Multi Test Cases
これもやるだけです。慌ててたので変数名がいまいちですが。
fun main() {
val t = readLine()!!.toInt()
val test = List(t) {
val n = readLine()!!.toInt()
val a = readLine()!!.split(" ").map { it.toInt() }
a.filter { it % 2 == 1 }.size
}
test.forEach {
println(it)
}
}
C - Count Connected Components
これは正直アルゴ式とかにそれっぽいのありそうだよね？と思って見たら実際あったのであんまり自分で考えていないです…
ただ、一応自力で解ける問題ではあったと思います。似たような問題はいくつか解いたことがあるので。
グラフの入力値の受け取り方とグラフのコード上の持ち方、DFSの基本的な書き方、スタックの拡張などはわりとテンプレに近いです。
過去記事だとこれが近いですかね？違うところもいろいろありますが。
DFSで、ある頂点から出発してそこから到達可能な頂点全てに訪れてそれを探索済としてマークします。そこから直接到達可能ということは、それが一つの連結成分に属しているということです。
それで、探索を開始する頂点としては
var graph = Array(1) { mutableListOf(1) }
fun main() {
Thread(
null,
{
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
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 seen = BooleanArray(n+1)
var ans = 0
for(i in 1..n) {
if(seen[i]) {
continue
}
dfs(i, seen)
ans++
}
println(ans)
},
"",
128 * 1024 * 1024
).start()
}
fun dfs(v: Int, seen: BooleanArray) {
seen[v] = true
for(node in graph[v]) {
if(seen[node]) {
continue
}
dfs(node, seen)
}
}
D - Happy New Year 2023
要するに
fun main() {
val t = readLine()!!.toInt()
repeat(t) {
val n = readLine()!!.toLong()
val result = primeFactorial(n)
val a = result.filter { it.second == 2L }
val b = result.filter { it.second == 1L }
println("${a.first().first} ${b.first().first}")
}
}
fun primeFactorial(paramN: Long): List<Pair<Long, Long>> {
val result = mutableListOf<Pair<Long, Long>>()
var n = paramN
var a = 2L
while(a * a <= n) {
if(n % a != 0L) {
a++
continue
}
var ex = 0L
while (n % a == 0L) {
ex++
n /= a
}
result.add(a to ex)
a++
}
if(n != 1L) {
result.add(n to 1)
}
return result
}
はい調子に乗ってすみません…
一応簡単に説明すると、primeFactorial()は素因数とその指数のペアを返します。
なのでこの問題の場合は、指数が2となっている数が
なので答えからそれらを線形探索として出力しています。線形探索といっても要素数が2なので実質定数時間です。TLEの原因は別にあるはずです。
primeFactorial()の計算量は、
じゃあ素因数分解をもっと高速に行う必要があるのかな？と思ったのですが、良い方法は見つけられず。
ここで気づいたのが、
primeFactorial()の処理の前半で素数を一つ見つけますが、一つ見つけたらそれを元に残りを求められるんじゃないかと。
素数を一つ見つけたとして、それを仮に
なので、
これでいけそうですね。
import kotlin.math.sqrt
fun main() {
val t = readLine()!!.toInt()
repeat(t) {
val n = readLine()!!.toLong()
val result = primeFactorial(n)
println("${result.first} ${result.second}")
}
}
fun primeFactorial(paramN: Long): Pair<Long, Long> {
mutableListOf<Pair<Long, Long>>()
var a = 2L
while (a * a <= paramN) {
if (paramN % a != 0L) {
a++
continue
}
val b = paramN / a
return if (b % a == 0L) {
a to b / a
} else {
sqrt(b.toDouble()).toLong() to a
}
}
return 0L to 0L
}
E - Count Simple Paths
さてEなんて普通なら自分に解けるはずはないのですが、見たところ頑張れば解けそうな感じがしたのでやってみました。
「単純」の意味がよくわかっていなかったのですがそこから調べて、自己ループや多重辺がないことで、サイクル（他の頂点を経由して自分のところの戻ってくる）はあるかもしれないということがわかりました。
たとえば入力例2のグラフは以下のようになります。
それで、この場合の答えは16ということですが、イメージを掴むために一通り列挙してみました。以下の16個ということみたいです。
1
1 2
1 2 3
1 2 3 4
1 2 4
1 2 4 3
1 3
1 3 2
1 3 2 4
1 3 4
1 3 4 2
1 4
1 4 2
1 4 2 3
1 4 3
1 4 3 2
なので、サイクルのせいで余計な探索をしてしまわないように注意してDFSで探索して数え上げればできそうな感じがしました。
ただ、実際それはどうすればいいのかというのを理解するのに時間がかかってしまいました。探索済の頂点を単純にそのようにマークするだけだと、必要な探索が実行されずに打ち切られてしまいます。
入力例2の場合、1 -> 2 -> 3 -> 4と探索するところまではいいのですが、次に2 -> 4やら1 -> 3やらを探索しようとした時、4や3はもう探索済と判断してしまってそこで終わってしまいます。
しかし実際に探索済であればガードしないといけないので、探索済かどうかの情報を正しく更新する必要があります。
結論としては、DFSの関数の最後でその時注目している頂点の探索済のマークを解除すればよかったようです。
なぜそれでうまくいくかというのは正直雰囲気でしかわかっていませんが、ざっくり以下のような感じになります。
上の1 -> 2 -> 3 -> 4と探索する例だと、4の探索後に4の探索済フラグが解除されます。続いて3の探索済フラグが解除され、2に戻ります。2から4に辿ろうとしますが、4の探索済フラグは解除されているので探索が続行されます。ここで4が再び探索済になります。4からは1、2、3に辿れますが、探索済フラグが立っていないのは3だけなのでそこに辿ります。3からは1、2、4に辿れますがいずれも探索済となっているのでそこで止まります。これで2、3、4は一旦一通り探索したので1に戻り、その過程で2、3、4の探索済フラグは解除されます。続いて1から3に辿ろうとしますが、3は未探索扱いになるので辿ります…と。
すみません、文章で書いても非常にわかりずらいとは思うのですが、図を描くほどの気力がなく…
まあとにかくこれでサイクルを回避しつつ探索できるので、あとは数え上げるだけです。これがわかったのはもうコンテスト終了直前…
上記の検証のためにコードの大枠はできていたので、大慌てで体裁を整えて終了30秒前くらいに提出したのが以下。
import kotlin.math.min
var graph = Array(1) { mutableListOf(1) }
fun main() {
Thread(
null,
{
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
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 seen = mutableMapOf<Int, Boolean>()
dfs(1, seen)
println(min(ans, 1000000))
},
"",
128 * 1024 * 1024
).start()
}
var ans = 0
fun dfs(v: Int, seen: MutableMap<Int, Boolean>) {
seen[v] = true
ans++
for(node in graph[v]) {
if(node == 1 || seen.getOrDefault(node, false)) {
continue
}
dfs(node, seen)
}
seen[v] = false
}
無念のTLE…
しかしACが29個なので大間違いってわけではないかも…？
そしてがっくりしつつ気づいたのが、1000000までいったらもう探索を打ち切っていいのではということ。
コンテストは終わっちゃったけど、試してみます。
import kotlin.math.min
var graph = Array(1) { mutableListOf(1) }
fun main() {
Thread(
null,
{
val (n, m) = readLine()!!.split(" ").map { it.toInt() }
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 seen = mutableMapOf<Int, Boolean>()
dfs(1, seen)
println(min(ans, 1000000))
},
"",
128 * 1024 * 1024
).start()
}
var ans = 0
fun dfs(v: Int, seen: MutableMap<Int, Boolean>) {
seen[v] = true
ans++
// ここだけ追加
if(ans > 1000000) {
return
}
for(node in graph[v]) {
if(node == 1 || seen.getOrDefault(node, false)) {
continue
}
dfs(node, seen)
}
seen[v] = false
}
ガッデム
感想
最後探索の打ち切りまで頭が回っていれば5完もあったかもと思うと悔しいのですが、それでもまあ4完で過去最高パフォで過去最高順位だったのでまあ喜んでおきます！
Cが解けたことやEがコンテスト後とはいえ解けたのはグラフの問題について多少勉強や練習をしたおかげで、Dが解けたのも以前素因数分解する問題に挑戦してその時の関数をライブラリ化しておいたおかげなので、やはり地道に取り組んでいけばそのうちいいことがあるのかなあと思いました。
単純に嬉しかった。楽しかった。これからもほどほどに頑張ります。
（執筆時間：1時間36分0秒）
Discussion