在编程竞赛(Competitive Programming)中使用 Kotlin

简单的示例: 可达数(Reachable Number)问题

我们来解决这个问题, 首先创建一个任意名称的 Kotlin 源代码文件. A.kt 也可以. 首先, 你需要实现题干部分指定的一个函数, 如下:

Kotlin 是一种注重实践、无固定成见的语言, 既支持命令式(imperative), 也支持函数式(function programming)编程风格, 并不强迫开发者使用哪一种. 你可以用函数式编程风格来实现函数 f, 使用 Kotlin 的尾递归(tail recursion) 功能:

tailrec fun removeZeroes(x: Int): Int =
    if (x % 10 == 0) removeZeroes(x / 10) else x

fun f(x: Int) = removeZeroes(x + 1)

或者, 你也可以为函数 f 编写命令式(imperative)的实现, 使用传统的 while 循环, 和可变的变量, 在 Kotlin 中表达为 var:

fun f(x: Int): Int {
    var cur = x + 1
    while (cur % 10 == 0) cur /= 10
    return cur
}

现在, 只需要编写 main 函数, 读取输入, 以及实现题目要求的算法的其他部分 — 通过标准输入给定的初始整数 n, 对它反复执行函数 f, 计算产生的不同的整数的个数.

默认, Kotlin 运行在 JVM 平台, 能够直接访问大量而且高效的库, 包括通用的集合与数据结构, 比如动态大小的数组 (ArrayList), 基于 hash 的 map 和 set (HashMap/HashSet), 基于树(tree) 的有序 map 和 set (TreeMap/TreeSet). 我们使用整数的 hash set 来追踪执行函数 f 时已经到达过的数值, 这个问题的简单的命令式编程风格的版本可以编写如下:

fun main() {
    var n = readln().toInt() // 从标准输入读取整数
    val reached = HashSet<Int>() // 可变的 hash set
    while (reached.add(n)) n = f(n) // 反复执行函数 f
    println(reached.size) // 将答案打印到标准输出
}

在编程竞赛中不需要处理输入错误的情况. 编程竞赛中的输入格式永远是正确的, 实际的输入不会与题目中描述的不同. 因此你可以使用 Kotlin 的 readln() 函数. 它假定输入字符串存在, 否则会抛出异常. 类似的, 如果输入字符串不是整数, String.toInt() 函数会抛出异常.

private fun readStr() = readln() // 读取单个字符串行
private fun readInt() = readStr().toInt() // 读取单个整数
// 对你的解答中需要用到的其他类型, 编写类似函数

注意这里使用了 private 可见度修饰符. 虽然可见度修饰符的概念与编程竞赛无关, 但通过使用它, 你可以从相同的代码模板创建多个解答文件, 而不会由于相同的包内存在多个同名的 public 声明而出现编译错误.

函数式操作符示例: 长数(Long Number)问题

fun main() {
    // 读取输入
    val n = readln().toInt()
    val s = readln()
    val fl = readln().split(" ").map { it.toInt() }
    // 定语局部函数 f
    fun f(c: Char) = '0' + fl[c - '1']
    // 贪婪查找第一个和最后一个下标
    val i = s.indexOfFirst { c -> f(c) > c }
        .takeIf { it >= 0 } ?: s.length
    val j = s.withIndex().indexOfFirst { (j, c) -> j > i && f(c) < c }
        .takeIf { it >= 0 } ?: s.length
    // 组合答案, 并输出
    val ans =
        s.substring(0, i) +
        s.substring(i, j).map { c -> f(c) }.joinToString("") +
        s.substring(j)
    println(ans)
}

在这段密集的代码中, 除了集合的变换之外, 你还看到很多 Kotlin 的便利功能, 比如局部函数, 以及 elvis 操作符 ?:, 它可以将惯用法 "如果值为正, 则使用这个值, 否则使用字符串长度", 写成简洁可读的表达式 .takeIf { it >= 0 } ?: s.length, 但是 Kotlin 也完全可以定义额外的值可变的变量, 以命令式的风格来表达同样的代码.

private fun readStr() = readln() // 读取单个字符串行
private fun readInt() = readStr().toInt() // 读取单个整数
private fun readStrings() = readStr().split(" ") // 读取多个字符串
private fun readInts() = readStrings().map { it.toInt() } // 读取多个整数

// 读取输入
val n = readInt()
val s = readStr()
val fl = readInts()

注意, 在编程竞赛中为变量取的名字, 经常会比实际工作中要短, 因为代码只编写一次, 之后就不再维护了. 但是, 这些变量名仍然遵守一些规则, 以便于记忆 — a 表示数组, i, j, 等等表示下标, r, 和 c 表述表中的行和列数, x 和 y 表示座标, 等等. 对输入数据使用与题目描述中相同的名称会比较简单. 但是, 更加复杂的问题要求更多的代码, 因此需要变量和函数的名称更长, 而且含义清晰.

在编程竞赛(Competitive Programming)中使用 Kotlin﻿

简单的示例: 可达数(Reachable Number)问题﻿

函数式操作符示例: 长数(Long Number)问题﻿

更多提示和技巧﻿

学习 Kotlin﻿

在编程竞赛(Competitive Programming)中使用 Kotlin

简单的示例: 可达数(Reachable Number)问题

函数式操作符示例: 长数(Long Number)问题

更多提示和技巧

学习 Kotlin