Задачи на Kotlin: ввод, вывод и инструменты

На алгоритмической секции (Яндекс, Т-Банк, Авито, Озон) можно писать на Kotlin, и задачи часто проверяет контест: программа читает stdin и печатает в stdout. Алгоритм тот же, что на любом языке, но на JVM есть свои грабли: медленный ввод, переполнение Int, глубокая рекурсия.

Шаблон программы

import java.io.*
import java.util.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().trim().toInt()
    val st = StringTokenizer(br.readLine())
    val a = IntArray(n) { st.nextToken().toInt() }

    val sb = StringBuilder()
    for (x in a) sb.append(x * 2).append('\n')
    print(sb)
}

• readln() удобен для одной-двух строк, но на 10^5 чисел readln().split(" ").map { it.toInt() } создаёт много объектов. BufferedReader плюс StringTokenizer надёжнее и быстрее.
• StreamTokenizer ещё быстрее для чисел, но читает их как Double: точно до 2^53, для Long около 10^18 не подходит.
• Вывод копим в StringBuilder и печатаем одним print. Сотни тысяч вызовов println по отдельности заметно медленнее.

Типы и переполнение

Int 32 бита (до 2 147 483 647), переполнение молчаливое. Суммы, произведения, расстояния в графах почти всегда в Long. Литерал Long пишется с L: 0L, 1_000_000_007L. Сравнение Long с литералом Int (x == 0) не компилируется, нужно x == 0L.

Для массивов чисел используйте IntArray/LongArray: Array<Int> хранит упакованные объекты и медленнее.

Полезная stdlib

• sorted(), sortedBy { }, sortedWith(compareBy({ it.a }, { it.b })); для IntArray есть sort() на месте;
• groupingBy { it }.eachCount() для частот, HashMap.merge(k, 1, Int::plus);
• kotlin.collections.ArrayDeque как стек и очередь: addLast, removeLast, removeFirst;
• java.util.PriorityQueue как куча (по умолчанию min; max через compareByDescending { it });
• TreeMap/TreeSet для floorKey, ceilingKey;
• binarySearch на отсортированном списке, но при повторах он возвращает любой подходящий индекс, для границ пишут свой поиск;
• maxOf(a, b), minOf, abs, a.coerceIn(lo, hi);
• repeat(n) { }, for (i in 0 until n), for (i in n - 1 downTo 0).

Осторожно с import java.util.*: он подменит ArrayDeque на Java-версию, у которой нет быстрого last(). Импортируйте Java-классы поимённо или помните про эту подмену.

Рекурсия

Стек потока JVM по умолчанию около 1 МБ (зависит от платформы и настроек). DFS по графу на 10^5 вершин в виде цепочки уронит StackOverflowError. Варианты: итеративный обход с явным стеком (лучше всего), tailrec для хвостовой рекурсии, запуск в Thread(null, ::solve, "main", 1 shl 26) с большим стеком.

Как вести себя на собесе

1. Уточнить ограничения: размер входа подсказывает нужную сложность (10^5 значит O(n log n), 10^3 допускает O(n²)).
2. Проговорить решение и сложность до кода.
3. Написать аккуратно, с понятными именами.
4. Прогнать вручную на примере и на краевых случаях: пустой ввод, один элемент, все одинаковые, отрицательные числа, максимальные значения.

Частые ошибки

• Int там, где нужен Long.
• Медленный ввод через readln().split() на больших данных.
• println в цикле на 10^5 строк.
• Рекурсивный DFS на глубоком графе.
• java.util.Stack и LinkedList как очередь вместо ArrayDeque.

Что спросят на собесе

• Как быстро читать ввод в Kotlin?
• Когда Int переполнится и как этого избежать?
• Какую структуру взять для стека, очереди, кучи?
• Почему рекурсивный DFS может упасть на JVM и что с этим делать?