🐙

AtCoder Beginner Contest 304参加記（A～C）

2023/06/04に公開

AtCoder

競プロ

tech

東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 304）に参加したので記録を書きます。
https://atcoder.jp/contests/abc304

今回は2完（しかも遅い）とかなり残念な結果に。コンテスト自体がUnratedになってしまったのでレーティングは下がらなかったものの、むしろ戒めとするために下がってほしかったまであります。

A - First Player

起点となる人を探して、まず起点から末尾まで出力、それから先頭から起点の一つ前まで出力という二段階で処理しました。添え字を計算で求めるのが正攻法かもしれないですが、絶対ミスるので可能な限り避けたく…

fun main() {
    val n = readLine()!!.toInt()
    val sa = List(n) {
        val (s, a) = readLine()!!.split(" ")
        s to a.toInt()
    }

    val min = sa.minBy { it.second }

    val index = sa.indexOf(min)

    for(i in index until n) {
        println(sa[i].first)
    }

    for(i in 0 until index) {
        println(sa[i].first)
    }
}

B - Subscribers

全部場合分けしようとしたり、切り捨てというのをなぜか桁自体を消し去るのと勘違いしたり、などしてグダグダでした。
最終的にはシンプルな実装に落ち着きましたが、だいぶ時間を食いました。

fun main() {
    val n = readLine()!!.toInt()

    val s = n.toString()
    if (n <= 1000 - 1) {
        println(n)
    } else {
        println(s.substring(0, 3) + "0".repeat(s.length - 3))
    }
}

C - Virus

愚直にやろうとしてTLEを繰り返して、結局解けませんでした。

import kotlin.math.sqrt

fun main() {
    val (n, d) = readLine()!!.split(" ").map { it.toInt() }
    val xy = List(n) {
        val (x, y) = readLine()!!.split(" ").map { it.toInt() }
        x to y
    }

    val eps = 1e-10

    val ans = BooleanArray(n)
    ans[0] = true

    val dd = d.toDouble()

    val map = mutableMapOf<Int, Double>()

    val new = mutableSetOf<Int>()

    var i = 0
    while(i < n) {
        val flg = i in new
        if(!ans[i] && !flg) {
            i++
            continue
        }

        if(flg) {
            new.remove(i)
        }

        val a = xy[i]

        var j = 0
        while (j < n) {
            if(i == j) {
                j++
                continue
            }

            if(ans[j]) {
                j++
                continue
            }

            val b = xy[j]

            val sum = double(a.first - b.first) + double(a.second - b.second)
            val dist = if(map.containsKey(sum)) {
                map[sum]!!
            } else {
                val tmp = sqrt((sum).toDouble())
                map[sum] = tmp
                tmp
            }

            if(dist - dd < eps) {
                ans[j] = true
                new.add(j)

                i = 0
                j = 0
            } else {
                j++
            }
        }
        i++
    }

    ans.forEach {
        if(it) {
            println("Yes")
        } else {
            println("No")
        }
    }
}

fun double(i: Int): Int {
    return i * i
}

このやり方だと、感染者が出た場合はそこを起点とする探索をまた新たに実行しないといけなくて計算量が膨れ上がりTLEとなりました。

実際には、グラフの問題としてとらえればよかったようです。感染があり得る距離の場合だけ辺があるグラフを作って、起点の1と同じ連結成分に含まれればよかったと。
辺を作る時点では感染しているかどうかは考えずに距離だけを見て処理すればよく、実際感染するかどうかは1と同じ連結成分に含まれるかどうかを調べる段階で判明すると。

fun main() {
    val (n, d) = readLine()!!.split(" ").map { it.toInt() }

    val xy = List(n) {
        val (x, y) = readLine()!!.split(" ").map { it.toInt() }
        x to y
    }

    val graph = Array(n) { mutableListOf<Int>() }

    for(i in 0 until n) {
        val a = xy[i]

        for(j in i + 1 until n) {
            val b = xy[j]

            val dist = ((a.first - b.first) * (a.first - b.first)) + ((a.second - b.second) * (a.second - b.second))
            if(dist <= d * d) {
                graph[i].add(j)
                graph[j].add(i)
            }
        }
    }

    val seen = BooleanArray(n)

    val queue = java.util.ArrayDeque<Int>()
    queue.add(0)

    val ans = BooleanArray(n)
    ans[0] = true

    while (queue.isNotEmpty()) {
        val v = queue.removeFirst()

        if(seen[v]) {
            continue
        }
        seen[v] = true

        for(node in graph[v]) {
            ans[node] = true
            queue.add(node)
        }
    }

    ans.forEach {
        if(it) {
            println("Yes")
        } else {
            println("No")
        }
    }
}

距離の判定と感染するかどうかの判定をごっちゃにしたのが良くなかったですね。分けて考えれば、「グラフを作る」「起点から辿れる範囲を全部探索する」だけで済むので…

感想

今回のCは解けるべき問題だったと思うので、残念ですね。一時休止していたのが思ったより響いてそう。復調まで時間がかかりそうだけど、続けていけばなんとかなるでしょう。焦らずに続けていきます。
それにしても、グラフは特に苦手意識はなかったんですけどね。まあ、直接的にグラフが入力される問題ばっかり解いていて、自分でグラフを作るような問題をあまり解いたことがなかったのもあるかもしれません。何にせよまだまだ解いた問題数が足りない。

（執筆時間: 33分29秒）

A - First Player

B - Subscribers

C - Virus

感想

Discussion