Kotlin для соревновательного программирования

Простой пример: задача «Достижимые числа»

Давайте рассмотрим конкретный пример.

Codeforces Round 555 проходил 26 апреля для 3-го дивизиона, что означает, что задачи подходят для попыток любым разработчикам. Вы можете использовать эту ссылку, чтобы ознакомиться с задачами. Самая простая задача в наборе — Задача A: Достижимые числа. Она требует реализации прямолинейного алгоритма, описанного в условии задачи.

Мы начнём решение, создав файл исходного кода Kotlin с произвольным именем. A.kt подойдёт. Сначала вам нужно реализовать функцию, указанную в условии задачи, как:

Обозначим функцию f(x) следующим образом: мы добавляем 1 к x, затем, пока в полученном числе есть хотя бы один конечный ноль, мы удаляем этот ноль.

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 необязательны во многих местах из-за повсеместного использования вывода типов, но каждое объявление всё же имеет хорошо определённый статический тип, известный на этапе компиляции.

Теперь всё, что осталось, — это написать главную функцию, которая считывает входные данные и реализует остальную часть алгоритма, требуемую условием задачи — вычислить количество различных целых чисел, получаемых при многократном применении функции f к начальному числу n, которое задаётся в стандартном входе.

По умолчанию Kotlin выполняется на JVM и предоставляет прямой доступ к богатой и эффективной библиотеке коллекций с универсальными коллекциями и структурами данных, такими как динамически изменяемые массивы (ArrayList), карты и множества на основе хешей (HashMap/HashSet), упорядоченные карты и множества на основе деревьев (TreeMap/TreeSet). Используя множество хешей целых чисел для отслеживания уже достигнутых значений при применении функции f, прямолинейная императивная версия решения задачи может быть записана следующим образом:

fun main() {
    var n = readln().toInt() // read integer from the input
    val reached = HashSet<Int>() // a mutable hash set 
    while (reached.add(n)) n = f(n) // iterate function f
    println(reached.size) // print answer to the output
}

fun main() {
    var n = readLine()!!.toInt() // read integer from the input
    val reached = HashSet<Int>() // a mutable hash set 
    while (reached.add(n)) n = f(n) // iterate function f
    println(reached.size) // print answer to the output
}

Все онлайн-соревнования по программированию позволяют использовать предварительно написанный код, поэтому вы можете определить свою собственную библиотеку служебных функций, ориентированных на соревновательное программирование, чтобы сделать ваш собственный код решения немного более читаемым и удобным для написания. Затем вы будете использовать этот код в качестве шаблона для своих решений. Например, вы можете определить следующие вспомогательные функции для чтения входных данных в соревнованиях по программированию:

private fun readStr() = readln() // string line
private fun readInt() = readStr().toInt() // single int
// similar for other types you'd use in your solutions

private fun readStr() = readLine()!! // string line
private fun readInt() = readStr().toInt() // single int
// similar for other types you'd use in your solutions

Обратите внимание на использование private модификатора видимости здесь. Хотя концепция модификатора видимости совершенно не относится к соревновательному программированию, она позволяет размещать несколько файлов решений на основе одного шаблона без получения ошибки из-за конфликтующих публичных объявлений в одном пакете.

Пример с функциональными операторами: задача «Большое число»

Для более сложных задач обширная библиотека функциональных операций над коллекциями Kotlin полезна для минимизации служебного кода и преобразования кода в линейную, последовательную и удобочитаемую цепочку преобразований данных. Например, задача Задача B: Большое число реализуется простым жадным алгоритмом, и её можно написать в таком стиле без одной изменяемой переменной:

fun main() {
    // read input
    val n = readln().toInt()
    val s = readln()
    val fl = readln().split(" ").map { it.toInt() }
    // define local function f
    fun f(c: Char) = '0' + fl[c - '1']
    // greedily find first and last indices
    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
    // compose and write the answer
    val ans =
        s.substring(0, i) +
        s.substring(i, j).map { c -> f(c) }.joinToString("") +
        s.substring(j)
    println(ans)
}

fun main() {
    // read input
    val n = readLine()!!.toInt()
    val s = readLine()!!
    val fl = readLine()!!.split(" ").map { it.toInt() }
    // define local function f
    fun f(c: Char) = '0' + fl[c - '1']
    // greedily find first and last indices
    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
    // compose and write the answer
    val ans =
        s.substring(0, i) +
        s.substring(i, j).map { c -> f(c) }.joinToString("") + 
        s.substring(j)
    println(ans)
}

В этом плотном коде, помимо преобразований коллекций, вы можете увидеть такие полезные функции Kotlin, как локальные функции и оператор выбора ?:, которые позволяют выразить выражения, такие как «взять значение, если оно положительно, или использовать длину», с компактными и читаемыми выражениями, такими как .takeIf { it >= 0 } ?: s.length, но вполне нормально в Kotlin создавать дополнительные изменяемые переменные и выражать тот же код в императивном стиле.

Чтобы сделать чтение входных данных в задачах соревновательного программирования, таких как эта, более компактным, можно иметь следующий список вспомогательных функций чтения входных данных:

private fun readStr() = readln() // string line
private fun readInt() = readStr().toInt() // single int
private fun readStrings() = readStr().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints

private fun readStr() = readLine()!! // string line
private fun readInt() = readStr().toInt() // single int
private fun readStrings() = readStr().split(" ") // list of strings
private fun readInts() = readStrings().map { it.toInt() } // list of ints

С помощью этих вспомогательных функций часть кода для чтения входных данных становится проще, тесно следуя спецификации входных данных в условии задачи строка за строкой:

// read input
val n = readInt()
val s = readStr()
val fl = readInts()

Обратите внимание, что в соревнованиях по программированию принято давать переменным более короткие имена, чем это типично в промышленном программировании, поскольку код нужно написать только один раз и не поддерживать его впоследствии. Однако эти имена обычно всё ещё являются мнемоническими — a для массивов, i, j, и другие для индексов, r, и c для номеров строк и столбцов в таблицах, x и y для координат и так далее. Легче сохранять те же имена для входных данных, что и в условии задачи. Однако более сложные задачи требуют большего объёма кода, что приводит к использованию более длинных, самодокументирующих имён переменных и функций.

Дополнительные советы и хитрости

Задачи по программированию для соревнований часто имеют такой ввод:

Первая строка ввода содержит два целых числа n и k

В Kotlin эту строку можно лаконично разобрать с помощью следующего оператора, используя распаковку переменных из списка целых чисел:

val (n, k) = readInts()

Возможно, будет соблазн использовать класс JVM java.util.Scanner для разбора менее структурированных форматов ввода. Kotlin разработан для хорошей работы с библиотеками JVM, поэтому их использование в Kotlin кажется вполне естественным. Однако будьте осторожны, что java.util.Scanner чрезвычайно медленный. Настолько медленный, что разбор 10⁵ или более целых чисел с его помощью может не вписаться в типичный лимит времени в 2 секунды, с которым справится простой Kotlin's split(" ").map { it.toInt() }

Вывод в Kotlin обычно прост с вызовами println(...) и использованием шаблонов строк Kotlin. Однако следует проявлять осторожность, когда вывод содержит порядка 10⁵ строк или более. Выдача стольких println вызовов слишком медленная, так как вывод в Kotlin автоматически сбрасывается после каждой строки. Более быстрый способ записи многих строк из массива или списка — использование функции joinToString() с "\n" в качестве разделителя, как это показано ниже:

println(a.joinToString("\n")) // each element of array/list of a separate line

Изучение Kotlin

Kotlin легко изучить, особенно для тех, кто уже знаком с Java. Краткое введение в базовый синтаксис Kotlin для разработчиков программного обеспечения можно найти непосредственно в разделе справки веб-сайта, начиная с основного синтаксиса.

IDEA имеет встроенный конвертер Java в Kotlin. Его могут использовать люди, знакомые с Java, для изучения соответствующих синтаксических конструкций Kotlin, но он не идеален, и все же стоит ознакомиться с Kotlin и изучить приемы программирования Kotlin.

Отличным ресурсом для изучения синтаксиса Kotlin и API стандартной библиотеки Kotlin являются Kotlin Koans.