Памятка гоферу про Яндекс.Контест (и похожие платформы)

Go — очень хороший язык для командной разработки высоконагруженных приложений, и не только для них. Для многих это основной язык разработки. А ещё он, пожалуй, наиболее удобный в освоении из современных языков бэкенда, поэтому для ненулевого количества начинающих Go — «родной» язык, самый близкий и комфортный. Видимо, поэтому изрядное количество программистов выбирают Go для решения алгоритмических задач.

В этом посте — несколько ценных советов тому, кто решил пойти этим путём. Мне бы такой пост очень помог год назад, но он мне тогда не попался (собственно, до сих пор не попался, поэтому пишу сам).

Ты точно этого хочешь?

Вообще-то Go плохо годится для олимпиадного программирования. Все те штуки, которыми Go ценен и за которые любим разработчиками, в олимпиадном программировании не нужны. Go вынуждает писать многословно и человекочитаемо; в решении алгоритмических задач, наоборот, писать нужно быстро, а читать этот код будет только компилятор. Так что главный совет: не надо. Не надо на Go решать задачки. Выучи Python, на худой конец — Javascript. Честное слово, это и для общего развития полезно, и в контестах повысит результаты кратно!

Ладно, ладно, задачки и на Go решаются, конечно. На пресловутом Leetcode решений на Go много, и многие гоферы практикуются именно там (тем, кто — нет, настоятельно рекомендую!) А вот если задачи приходится решать на других платформах, возникают неожиданные проблемы…

На нашей бывшей ⅙ части суши самая «ходовая» платформа — Яндекс.Контест, больше половины всех и всяческих конкурсов проводятся именно на ней¹. От Leetcode тут есть важное отличие: требуется обрабатывать стандартный ввод, а результаты выводить в стандартный вывод (эта схема встречается и на других платформах, причём не только на импортозамещённом Leetcode от Яндекса). Это накладывает дополнительные ограничения, о которые гоферы, судя по чатам, регулярно спотыкаются.

Ввод

Главный камень преткновения — ввод. Забудь про fmt.Scan() и иже с ним — это медленно; можно запросто исчерпать лимит времени, не закончив читать входные данные. Твой друг — bufio.Scanner; 99% моих решений выглядят так:

package main

import (
    bufio
	<остальные импорты>
)

func main() {
	s := bufio.NewScanner(os.Stdin)
	s.Split(bufio.ScanWords)

    <дальше, собственно, решение>
}

Если будешь сохранять это в файлик с шаблоном решения (такой есть смысл завести), добавь туда ещё вот такую функцию:

func readInt(s *bufio.Scanner) int {
	s.Scan()
	n, _ := strconv.Atoi(s.Text())
	return n
}

Вывод

Вывод в fmt работает быстрее, так что без fmt обычно всё равно никуда (это не повод использовать fmt.Printf() и аналоги: строка форматирования парсится при каждом вызове, это очень долго). Проблемы возникают, когда надо вывести набор значений через пробел (как правило, это какой-то массив или слайс). Есть соблазн написать что-то наподобие

func printSlice[T any](slice []T) {
    for i, v := range slice {
        fmt.Print(v)
        if i < len(slice)-1 {
            fmt.Print(" ")
        }
    }
    fmt.Println()
}

Разумеется, уже при длине slice порядка 10⁶ такое не «пролезет» в лимит по времени. По-хорошему, тут надо пользоваться strings.Builder, и потом выводить строку за один fmt.Println(), но если время поджимает…

p := fmt.Sprint(slice)
fmt.Println(p[1:len(p)-1])

Это, конечно, грязный хак², и отрабатывает (на длинных слайсах) примерно вдвое дольше, чем через strings.Builder, зато всего две строчки.

Удачи в контестах, гофер!