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⁵ или более целых чисел с его помощью может не поместиться в типичный лимит времени в 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.