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 readInt() = readln().toInt()
private fun readStr() = readln().toString()
// similar for other types you'd use in your solutions

private fun readInt() = readLn().toInt()
private fun readStr() = readLn().toString()
// 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, как локальные функции и оператор Elvis ?:, которые позволяют выражать идиомы, такие как «взять значение, если оно положительное, или в противном случае использовать длину», с лаконичными и читаемыми выражениями, такими как .takeIf { it >= 0 } ?: s.length, но в Kotlin вполне допустимо создавать дополнительные изменяемые переменные и выражать тот же самый код в императивном стиле.

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

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

private fun readLn() = readLine()!! // string line
private fun readInt() = readLn().toInt() // single int
private fun readStrings() = readLn().split(" ") // list of strings

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

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

// read input
val n = readInt()
val s = readLn()
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⁵ или более целых чисел с его помощью может не уложиться в типичный двухсекундный лимит времени, который легко обрабатывается простым split(" ").map { it.toInt() } Kotlin.

Выдача вывода в 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.