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, как локальные функции и оператор elvis operator ?:, которые позволяют выразить идиомы, такие как «взять значение, если оно положительное, или в противном случае использовать длину», с помощью лаконичных и читаемых выражений, таких как .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-метода 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.