Kotlinで競プロをするTips

これは何

• Kotlinで競プロするときに役立ったTipsを随時追記します。
• Kotlinに関係のない競プロのTipsも含みます。

Tips

出力の高速化

大量に出力すると、場合によってはTLEします。

val ans = List(2_000_000_000) { 1 }
ans.forEach { println(it) }

出力は繰り返さず、一回にまとめるとよいです。

println(ans.joinToString("\n"))

List, Set, Arrayへの要素追加速度

プリミティブ型配列は要素の追加が速いので、使える場面では積極的に使うとよいです。MutableSetは要素追加に時間がかかるので、使い所に注意が必要です。

fun main() {
    val size = 20_000_000

    measureTimeMillis {
        val l = IntArray(size)
        for (i in 0 until size) l[i] = i
    }.also { println("$it ms") } // 35 ms

    measureTimeMillis {
        val l = mutableListOf<Int>()
        for (i in 0 until size) l.add(i)
    }.also { println("$it ms") } // 637 ms

    measureTimeMillis {
        val l = mutableSetOf<Int>()
        for (i in 0 until size) l.add(i)
    }.also { println("$it ms") } // 1550 ms
}

深い再帰に注意

関数の再帰は複雑な処理を見通しよく書けて便利ですが、スタックを使う特性上、再帰が深くなりすぎるとスタックオーバーフローを起こします。

// 木構造で自分より上の階層のnodeが持つpointを合算する (再帰)
fun dfs(current: Int, now: Long) {
    points[current] += now
    for (next in graph[current]) }
        if (depth[next] > depth[a]) dfs(next, points[current])
    }
}
dfs(0, 0) // 木が深いと実行時例外が発生する場合がある

再帰が深くなることが予想される場合は、末尾再帰の形式にするか、キューやスタックを使って単純なループ処理にするのがよいでしょう。

// 木構造で自分より上の階層のnodeが持つpointを合算する (キューを使ったループ)
val queue = ArrayDeque<Int>()
queue.addLast(0)
while (queue.isNotEmpty()) {
    val current = queue.removeLast()
    for (next in graph[current]) {
        if (depth[next] > depth[current]) {
            points[next] += points[current]
            queue.addLast(next)
        }
    }
}