🗂

AtCoder Beginner Contest 284 A~Eのメモ

2023/01/08に公開約8,700字

AtCoder Beginner Contest 284(ABC284)に参加したので記録を残します。

https://atcoder.jp/contests/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の基本的な書き方、スタックの拡張などはわりとテンプレに近いです。

過去記事だとこれが近いですかね?違うところもいろいろありますが。
https://zenn.dev/dhirabayashi/articles/f488dc315de15d

DFSで、ある頂点から出発してそこから到達可能な頂点全てに訪れてそれを探索済としてマークします。そこから直接到達可能ということは、それが一つの連結成分に属しているということです。

それで、探索を開始する頂点としては1からNまで全てを試します。しかし、探索済だったらスキップして答えとしてカウントしません。探索済ということは、他の連結成分に属しているということだからです。逆に、未探索であれば未知の連結成分が見つかったということなので答えとしてカウントします。そして、その連結成分が再度カウントされることがないように一通り探索して探索済としてマークします。

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)
    }
}

Nが小さいので計算量についてはあまり考えなくても大丈夫そうです。

D - Happy New Year 2023

要するにNを素因数分解すればいいんですね?素因数分解なら以前やってその時の関数を残してあるからそれを貼るだけ!いやー楽ちんだわー

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となっている数がp、1となっている数がqであるはず、ということで書いています。
なので答えからそれらを線形探索として出力しています。線形探索といっても要素数が2なので実質定数時間です。TLEの原因は別にあるはずです。

primeFactorial()の計算量は、O(√N)のはずです。これじゃダメなのかな?と思ってここでようやく計算量を考えてみたのですが(先にやれ)、Nの最大値は9 × 10^{18}なんですね。ということは、√N3 × 10^{9}です。30億。これはたしかに無理ですね。

じゃあ素因数分解をもっと高速に行う必要があるのかな?と思ったのですが、良い方法は見つけられず。

ここで気づいたのが、N = p^2qp, qは相異なる素数)とわかっているのだから、最後まで素因数分解を最後までやりきる必要はないんじゃない?ということでした。
primeFactorial()の処理の前半で素数を一つ見つけますが、一つ見つけたらそれを元に残りを求められるんじゃないかと。

素数を一つ見つけたとして、それを仮にaとしますが、このapqのどちらかなわけです。
N = p^2qなので、apだとしたらN ÷ apqaqであればN ÷ ap^2です。
なので、N ÷ aをさらにaで割った余りが0であればap0でなければaqとわかります。
apだとしたらN ÷ a ÷ aq(割り切れる)、aqであればN ÷ a ÷ ap^2 / q(割り切れない)となります。(p, qは相異なる素数なので後者が割り切れることはない)
これでいけそうですね。

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
}

apであればqは割り算だけで求められますが、aqであればpは平方根を計算しないと求められません。精度とか大丈夫かなと心配でしたが、大丈夫だったみたいです。

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完で過去最高パフォで過去最高順位だったのでまあ喜んでおきます!

https://twitter.com/dhirabayashi64/status/1611727458822393856

Cが解けたことやEがコンテスト後とはいえ解けたのはグラフの問題について多少勉強や練習をしたおかげで、Dが解けたのも以前素因数分解する問題に挑戦してその時の関数をライブラリ化しておいたおかげなので、やはり地道に取り組んでいけばそのうちいいことがあるのかなあと思いました。

単純に嬉しかった。楽しかった。これからもほどほどに頑張ります。

(執筆時間:1時間36分0秒)

Discussion

ログインするとコメントできます