📑

AtCoder Beginner Contest 333参加記（A～D）

2023/12/17に公開

AtCoder

競プロ

tech

トヨタ自動車プログラミングコンテスト2023#8（AtCoder Beginner Contest 333）に参加したので記録を残します。
https://atcoder.jp/contests/abc333

今回は4完です。

A - Three Threes

Stringのrepeat()で同じ文字が連続した文字列を作れるのでそれを使いました。

fun main() {
    val n = readln().toInt()

    println(n.toString().repeat(n))
}

B - Pentagon

数学はできませんので、見た瞬間ちょっとたじろぎました。
ひとまず正五角形なので各辺の長さは全て等しいはずなので、与えられた入力が2つとも辺なら答えはYesなのはわかります。
対角線なら辺の長さとは違いそうですが… と考えると、各点から引ける対角線は2本しかないことと、対角線は全て同じ長さのはずだということに気づきました。なので、与えられた入力が2つとも辺、もしくは2つとも対角線ならYes、そうでなければNoと言えそうです。

fun main() {
    val s = readln().toList().sorted().joinToString("")
    val t = readln().toList().sorted().joinToString("")

    var list = listOf("AB", "BC", "CD", "DE", "AE")

    if(s in list && t in list) {
        println("Yes")
        return
    }

    list = listOf("AC", "AD", "BE", "BD", "CE")
    if(s in list && t in list) {
        println("Yes")
	
        return
    }

    println("No")
}

あまり実装としてはいけてないのですが、入力値としてあり得る値のバリエーションは少ないので全部ベタ書きしました。ABとBA、などは同一視したいので入力値は最初に辞書順に並べ替えています。

C - Repunit Trio

レピュニットという言葉があるんですね。知らなかった。

最初は、あり得そうな数を列挙してそれが該当の値かどうか判定して、みたいなことを考えてみました。構成する数は1, 2, 3だけであること、文字列として見ると辞書順に並ぶこと、1の位の数は絶対に3、などの性質があることは気づきました。
ただ、そのようなことは考えなくても、そもそもレピュニットの数がそんなに多くないことにも気づきました。（時間がかかりましたが）
よく見ると例3がかなり親切ですね。入力は制約の最大値で、出力で使用されるレピュニットの最大値は111111111111であることがわかります。つまり、この問題に関係のあるレピュニットは1, 11, 111, ..., 111111111111の12個しかありません。それなら3重ループで組み合わせを全探索しても全く問題なしです。
組み合わせで3つの和のリストを作って、重複を排除して、ソートして、そしたらそのうちの $N$ 番目の値が答えとなります。

fun main() {
    val n = readln().toInt()

    val parts = (1..12).map { "1".repeat(it).toLong() }

    val list = mutableListOf<Long>()
    for(a in parts) {
        for(b in parts) {
            for(c in parts) {
                val num = a + b + c
                list.add(num)
            }
        }
    }

    println(list.distinct().sorted()[n-1])
}

D - Erase Leaves

けっこうシンプルなグラフの問題です。サクッと解きたかったのですが、けっこうハマってしまいました。

制約から $O(N)$ でも大丈夫なので、DFSとかで数える方針を考えました。各頂点ごとに、その頂点にぶら下がる頂点の数（自身を含む）がわかれば、それがその頂点を取り除くために必要な操作回数になります。であれば、それらの値のうち1に隣接する頂点の値だけ見て、そのうちの最小値を取り出して、1自身を取り除く操作のために+ 1したら答えじゃないかと最初は思いました。

ただ、それだと例3で出力が合いません。考えてみたら、1に隣接する頂点が3つ以上ある場合、そのうちの1つを除去しても1は葉にならないので、まだ1を除去できません。1つを残してそれ以外は全部除去する必要がありました。なので1に隣接する頂点のうち、最大の値を持つ頂点以外の値を全部足して、それに1を足した値が答え、というのが正しかったです。

しかしそれでもまだダメで、WAが出てしまいました。

考え方としては合ってそうだったのですが、上の実装だと1に隣接する頂点が葉だった場合にその頂点が持つ値が0となってしまい、うまくいかないことがわかりました。
じゃあその場合は1にしてしまおう、という方針で書き換えたら通りました。

import kotlin.math.min
import kotlin.system.exitProcess

var n = 0
var memo = IntArray(n + 1)

fun main() {
    Thread(
        null,
        {
            n = readln().toInt()
            memo = IntArray(n + 1)

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

            val br = System.`in`.bufferedReader()

            repeat(n - 1) {
                val (u, v)  = br.readLine().split(" ").map { it.toInt() }
                graph[u].add(v)
                graph[v].add(u)
            }

            val seen = BooleanArray(n + 1)

            dfs(1, seen, graph)

            val ans = list.map { memo[it] }
                .map { if(it == 0) 1 else it }
                .sorted()
                .dropLast(1)
                .sum() + 1

            println(ans)
        },
        "",
        128 * 1024 * 1024
    ).start()
}

val list = mutableListOf<Int>()

fun dfs(v: Int, seen: BooleanArray, graph: Array<MutableList<Int>>): Int {
    if(seen[v]) {
        return 0
    }
    seen[v] = true

    // 葉
    if(graph[v].size == 1) {
        if(v == 1) {
            println(1)
            exitProcess(0)
        }

        return 1
    }

    var sum = 1
    for(node in graph[v]) {
        if(seen[node]) {
            continue
        }
        // 1に隣接する
        if(v == 1) {
            list.add(node)
        }

        sum += dfs(node, seen, graph)
    }
    memo[v] = sum

    return sum
}

なお、他にも1自身が葉である場合もコーナーケースとなります。1が葉であれば答えは必ず1です。例2がそうなっているので、それでハマることはありませんでした。

それにしても、遅いですね。DFSを書くといつもこんな感じなのですが…

なお解説を見てみましたが、Union-Findを使うともっと簡単に書けるようですね。

fun main() {
    val n = readln().toInt()

    val uf = UnionFind(n + 1)

    val br = System.`in`.bufferedReader()
    repeat(n - 1) {
        val (u, v) = br.readLine().split(" ").map { it.toInt() }
        if(u != 1) {
            uf.union(u, v)
        }
    }

    val max = (1..n).map { uf.find(it) }.groupBy { it }.map { it.value.size }.max()
    println(n - max)
}

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に隣接する頂点と1をつなぐ辺は引かず、それ以外を引くと森ができる。その連結成分のうち大きさが最大のものを $N$ から引けば答え、と。言われてみればたしかに、ですね。
Union-Findの応用に慣れてないなあ。今回の問題は連結成分の大きさが重要ってことだったのですが、連結成分と聞いたらUnion-Findを思い出すべきなのかな。

感想

Dはあまり時間かからず通したかったのですが、実際にはDを通したのはけっこう時間ギリギリになってしまいました。しかも上に書いた以外にもWAを出していて合計2ペナ。間に合ってよかった…
満足していいかはわからないですが、残り時間が少ない中で2ペナしてもパニックにならずに考えて答えを見つけることができたのは、まあ以前よりは成長しているのかもしれません。
当たり前っちゃ当たり前なんですが、やはり答えは落ち着いて考えて見つけるしかないですね。WAを出し続けて慣れて耐性ができて、パニックになりにくくなったのかも。WAの数だけ強くなれるよ。
（執筆時間: 57分46秒）

A - Three Threes

B - Pentagon

C - Repunit Trio

D - Erase Leaves

感想

Discussion