【第40回アルゴリズム勉強会】参加記

久しぶりに行って来ました勉強会。
今日のスケジュールはこんな感じ。
言語はKotlinでやっています。
初心者の僕には★だけかな＞＜

yukicoder

• yukicoder No.431 ★
• yukicoder No.419 ★
• yukicoder No.94 ★★★

No.431 死亡フラグ

No.431 死亡フラグ - yukicoder

fun main(args: Array<String>) {
    val flags : List<Int> = readLine()!!.split(" ").map { it.toInt() }
    if (isDead(flags)) {
        println("DEAD")
    } else {
        println("SURVIVED")
    }
}

fun isDead(flags : List<Int>) : Boolean {
    if (flags.last() == 1) {
        return false
    } else {
        return flags.sum() >= 2
    }
}

3つの死亡フラグと1つの生存フラグ
isDead関数で、生存フラグがあればtrue
死亡フラグの合計が2以上かどうかの真偽値で判定

No.419 直角三角形

No.419 直角三角形 - yukicoder

fun main(args: Array<String>) {
    val a_b : List<Int> = readLine()!!.split(" ").map { it.toInt() }
    val result = "%.10f".format(getThirdSide(a_b))
    println(result)
}

fun getThirdSide(ab : List<Int>) : Double {
    val a = ab.first().toDouble()
    val b = ab.last().toDouble()
    if (a == b) {
        val c2 = Math.pow(a, 2.0) + Math.pow(b, 2.0)
        return Math.sqrt(c2)
    } else if (a > b) {
        val c2 = Math.pow(a, 2.0) - Math.pow(b, 2.0)
        return Math.sqrt(c2)
    } else {
        val c2 = Math.pow(b, 2.0) - Math.pow(a, 2.0)
        return Math.sqrt(c2)
    }
}

2辺から直角三角形の残りの1辺を求めます。
与えられた2辺が等しいときは、90°, 45°, 45° のパターンしかないので、

等しくないときは大きい辺から引く感じで

プログラム上では、大小場合わけしてますが絶対値を取ればコード量が減ったなぁと

No.94 圏外です (EASY)

No.94 圏外です。(EASY) - yukicoder

これはリタイアです。
当然愚直にやったら計算量多くなるしなぁと考えていて時間切れ。
これはUnionFind木で解けるとのこと。
それについては、以下のスライドに任せるとして

Union find(素集合データ構造) from AtCoder Inc.

www.slideshare.net

この問題では、通信可能圏のグループを用意してやり、
それぞれのグループが持つ最大値から更に最大値を出力するという感じです。
写経したコードはこんな感じ。

fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    if (N == 0) {
        println(1)
        return
    }

    val X = Array(N, {0})
    val Y = Array(N, {0})

    (0 until N).forEach {
        val xy = readLine()!!.split(" ").map { it.toInt() }
        X[it] = xy.first()
        Y[it] = xy.last()
    }

    val union = UnionFind(N)

    (0 until N).forEach { i ->
        (i+1 until N).forEach { j ->
            if (distNotSqrt(X[i] - X[j], Y[i] - Y[j]) <= 100) {
                union.union(i, j)
            }
        }
    }

    var mx = 0
    (0 until N).forEach { i ->
        (i+1 until N).forEach { j ->
            if (union.isSame(i, j)) {
                val len = distNotSqrt(X[i] - X[j], Y[i] - Y[j])
                if (mx < len) mx = len
            }
        }
    }
    println(Math.sqrt(mx.toDouble()) + 2)
}

fun distNotSqrt(a: Int, b: Int) = a * a + b * b

class UnionFind(N : Int) {
    val parent = Array(N, { i -> i })
    val rank = Array(N, { 0 })

    fun union(a : Int, b : Int) : Boolean {
        val Aroot = find(a)
        val Broot = find(b)
        if (Aroot == Broot) return false

        if (rank[Aroot] > rank[Broot]) {
            parent[Broot] = Aroot
        } else if (rank[Aroot] < rank[Broot]) {
            parent[Aroot] = Broot
        } else {
            parent[Aroot] = Broot
            rank[Broot]++
        }
        return true
    }

    fun find(a : Int) : Int {
        if (parent[a] == a) {
            return a
        } else {
            return find(parent[a])
        }
    }

    fun isSame(a : Int, b : Int) : Boolean = find(a) == find(b)
}

union.unionって感じになるの命名ミスあかんのではと思います。
あと、あんまりKotlinっぽさを出せてないのではとも感じますね……。

いやー、★★★は難敵というか要知識って感じねやっぱ。