改进翻译

竞技程序设计

作者	Roman Elizarov，灰蓝天际（翻译）

本教程介绍了 Kotlin 在竞技性程序设计中的基本用法。

先决条件

本教程适用于之前未使用 Kotlin 的竞技程序员，也适用于之前从未参与过任何竞技性程序设计活动的 Kotlin 开发人员。本教程假定读者具有相应的编程技能。

竞技程序设计与 Kotlin

竞技性程序设计是一项智力运动，参赛选手在严格的限制条件下编写程序精确地解决指定的算法问题。问题可以简单到任何软件开发人员都能解题、只需很少代码就能得到正确答案，也可以复杂到需要特殊的算法、数据结构知识以及大量实践。虽然 Kotlin 不是专为竞技性编程而设计的，但是它恰好适合这一领域，显著减少了程序员所需编写与阅读的样板代码量，这样几乎可以像动态脚本语言一样编写代码，同时又有静态类型语言的工具与性能支持。

关于如何搭建 Kotlin 开发环境，请参见以 IntelliJ IDEA 入门。在竞技程序设计中，通常会创建单个项目，而每个问题的答案写在单个源文件中。

简单示例：可达数问题

我们来看一个具体的示例。

Codeforces 第 555 轮第 3 次分赛已于 4 月 26 日举行，意味着它有适合任何开发者尝试的问题。可以打开这个链接来阅读问题。这组问题中最简单的是问题 A：可达数。它要求实现问题陈述中所描述的简单算法。

我们会通过创建一个任意名称的 Kotlin 源文件来解这个问题。A.kt 就挺好。首先，我们需要实现问题陈述中指定的函数，如下：

我们以这样的方式来表示函数 f(x)：将 x 加 1，然后，如果得到的数至少以一个零结尾，就去掉这个零。

Kotlin 是一门实用且不拘一格的语言，既支持命令式也支持函数式编程风格，而不会将开发人员推向任何一种风格。可以按函数式风格实现函数 f，使用像尾递归这样的 Kotlin 特性：

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

也可以编写函数 f 的命令式实现，使用传统的 while 循环与可变变量（在 Kotlin 中用 var 表示）：

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

由于普遍使用类型推断，在 Kotlin 中很多地方的类型都是可选的，不过每个声明仍然具有编译期已知的明确定义的静态类型。

现在就只剩编写读取输入的主函数并实现问题陈述所要求算法的其余部分——计算在对标准输入所给出的初始数 n 重复应用函数 f 时所产生的不同整数的个数。

默认情况下，Kotlin 在 JVM 上运行，可以直接访问丰富且高效的集合库，其中包含通用的集合与数据结构，如动态大小的数组（ArrayList）、基于哈希的 map 与 set（HashMap/HashSet）、基于树的 map 与 set（TreeMap/TreeSet）等。使用整数哈希 set 来跟踪应用函数 f 时已达到的值，该问题解法的一个简单命令式版本可以这样编写：

fun main() {
    var n = readLine()!!.toInt() // 读取输入的整数
    val reached = HashSet<Int>() // 可变的哈希 set
    while (reached.add(n)) n = f(n) // 迭代函数 f
    println(reached.size) // 输出答案
}

请注意在 readLine() 函数调用之后使用了 Kotlin 的空断言操作符 !!。 Kotlin 的 readLine() 函数定义成了返回可空类型 String?，并且会在输入结束时返回 null，这样明确迫使开发人员处理输入缺失的情况。

在竞技程序设计中无需处理输入格式错误的情况。竞技程序设计中的输入格式向来都是精确指定的，并且实际输入不能偏离问题陈述中的输入规范。这基本上就是空断言操作符 !! 的行为—— 它断言输入的字符串存在，如不存在则抛出异常。同样，如果输入不是整数，那么 String.toInt() 函数会抛出异常。

所有在线竞技程序设计活动都允许使用预编写代码，因此可以定义自己的面向竞技程序设计的工具函数库，以使实际解题代码更易于读写。然后，可以使用该代码作为解题模板。例如，可以定义以下辅助函数来读取竞技程序设计中的输入：

private fun readLn() = readLine()!!
private fun readInt() = readLn().toInt()
// 用于在解题中会用到的其他类型的类似声明等

请注意这里使用了 private（私有）可见修饰符。虽然可见性修饰符的概念与竞技程序设计并无瓜葛，但是它让你能够将基于相同模板的多个解题文件放在同一包中，而不会出现公有声明冲突的报错。

函数式操作示例：长数问题

对于更复杂的问题，Kotlin 丰富的集合函数式操作库就派上用场了，可以大幅减少模板代码，并将代码写成从上到下、从左到右的流式数据转换流水线。例如问题 B：长数问题用一个简单的贪心算法实现，可以采用这种风格编写而无需任何可变变量：

fun main() {
    // 读取输入
    val n = readLine()!!.toInt()
    val s = readLine()!!
    val fl = readLine()!!.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)
}

在这段密集的代码中，除了集合转换之外，还可以看到像局部函数以及 elvis 操作符 ?: 这样灵便的 Kotlin 特性，通过 elvis 操作符，可以用简洁易读的表达式如 .takeIf { it >= 0 } ?: s.length 来表达类似“如果是正数就取其值，否则取长度”的惯用法，当然，也完全可以使用 Kotlin 创建额外的可变变量并以命令式风格表达相同的代码。

为了让这种竞技程序设计任务中读取输入更简洁，可以使用以下输入读取辅助函数列表：

private fun readLn() = readLine()!! // 字符串行
private fun readInt() = readLn().toInt() // 单个整数
private fun readStrings() = readLn().split(" ") // 字符串列表
private fun readInts() = readStrings().map { it.toInt() } // 整数列表

有了这些辅助函数，读取输入的代码部分变得更简单，一行行地严格遵循问题陈述中的输入规范：

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

请注意，在竞技程序设计中，习惯给变量取比通常在工业编程实践中更短的名称，因为代码只需编写一次，以后就不用支持了。当然，这些名称通常仍然是助记手段——数组用 a，索引用 i、j，表格的行列号用 r、c，坐标用 x、y 等。输入数据的名称保持与问题陈述中所给出的名称相同也更容易。当然，越复杂的问题就越需要更多的代码来解，这导致更长、具有自解释性的变量名与函数名。

学习 Kotlin

Kotlin 旨在让已经了解 Java 的人易于学习。在官方比较页上给出了二者差异的快速概述。对于软件开发人员来说，关于 Kotlin 基本语法的简短介绍可以直接在以基本语法开始的网站参考部分中直接找。

IDEA 已内置 Java-to-Kotlin 转换器。熟悉 Java 的人可以用它来学习相应的 Kotlin 语法结构，但它并不完美，并且你仍然需要自己熟悉 Kotlin 并学习 Kotlin 惯用法。

学习 Kotlin 语法以及 Kotlin 标准库 API 的一个很好的资源是 Kotlin 心印。