ZONeエナジー プログラミングコンテストの2nd ROUNDに挑戦してました

連休中にTwitterの広告で見かけたのでこっそり解いてました。
長らくこの手のプログラムは書いていませんでしたが、気楽に解ける感じで純粋にアルゴリズムだけをやるのは楽しかったです。
mh-procon.zone-energy.jp
使用言語はKotlin。

1問目

与えられた文字列のROT13 - Wikipediaを出力する。

• a → 0
• b → 1
• z → 25

にマッピングして、26を法とする減算で求めるといい感じ。

fun main() {
    val builder = StringBuilder()

    val ALL_NUM = 26

    while (true) {
        try {
            val input = readInputLine()

            builder.appendln(input.map { c -> 'a' + (c - 'a' + 13) % ALL_NUM }.joinToString(""))
        } catch (e: Exception) {
            break
        }
    }

    print(builder.toString())
}

fun readInputLine(): String {
    return readLine()!!
}

2問目

2次元行列の中から素数の数を数え上げる。重複はそれぞれ別にカウントする。*1
事前にエラトステネスの篩 - Wikipediaにて前処理をしておくといい感じ。*2

import kotlin.math.sqrt

fun main() {
    val builder = StringBuilder()

    val NUM_MAX = 999

    val isPrime = BooleanArray(NUM_MAX + 1) { true }

    isPrime[0] = false
    isPrime[1] = false

    for (i in 2..sqrt(NUM_MAX.toDouble()).toInt() + 1) {
        if (isPrime[i]) {
            for (j in i * 2..NUM_MAX step i) {
                isPrime[j] = false
            }
        }
    }

    var ans = 0

    while (true) {
        try {
            val input = readInputLine()

            input.split(" ").forEach {
                val i = it.toInt()
                if (isPrime[i]) {
                    ans++
                }
            }
        } catch (e: Exception) {
            break
        }
    }

    builder.appendln(ans)

    print(builder.toString())
}

fun readInputLine(): String {
    return readLine()!!
}

3問目

与えられた連結グラフについて、任意の3つのノードの組み合わせの中からそのノードと隣接するノードの総数が最も多い組み合わせを選択する。
予め連結リストを作成して解きました。計算量は(のはず)ですが制約がゆるゆるなので解を出すには十分速いです。

fun main() {
    val builder = StringBuilder()

    val (n, m) = readInputLine().split(" ").map { it.toInt() }

    val connection = Array(n) { mutableSetOf<Int>() }

    repeat(m) {
        val (a, b) = readInputLine().split(" ").map { it.toInt() }
        connection[a].add(b)
        connection[b].add(a)
    }

    var maxNum = 0

    var ans1 = -1
    var ans2 = -1
    var ans3 = -1

    for (i in 0 until n) {
        for (j in 0 until n) {
            for (k in 0 until n) {
                val allPlanet = mutableSetOf<Int>()
                allPlanet.add(i)
                allPlanet.add(j)
                allPlanet.add(k)

                allPlanet.addAll(connection[i])
                allPlanet.addAll(connection[j])
                allPlanet.addAll(connection[k])

                if (allPlanet.size > maxNum) {
                    maxNum = allPlanet.size
                    ans1 = i
                    ans2 = j
                    ans3 = k
                }
            }
        }
    }

    builder.appendln("$ans1 $ans2 $ans3")

    print(builder.toString())
}

fun readInputLine(): String {
    return readLine()!!
}

*1:最初重複は1つとしてカウントするものと勘違いして出力形式が違うのかといろいろやってました

*2:なお、最初空でコード書いていたらのコードを書いていました……元水コーダーが聞いてあきれますね