Стивен Халим , Феликс Халим - Спортивное программирование

Стивен Халим, Феликс Халим

Спортивное программирование

Competitive
Programming 3
The New Lower Bound of Programming Contests

Steven Halim, Felix Halim

Спортивное
программирование
Новый нижний предел соревнований по программированию

Стивен Халим, Феликс Халим

Москва, 2020

УДК 004.02, 004.424
ББК 22.18
Х17

Х17

Халим С., Халим Ф.
Спортивное программирование / пер. с англ. Н. Б. Желновой, А. В. Снас­
тина. – М.: ДМК Пресс, 2020. – 604 с.: ил.
ISBN 978-5-97060-758-9
Книга содержит задачи по программированию, аналогичные тем, которые
используются на соревнованиях мирового уровня (в частности, ACM ICPC и IOI).
Помимо задач разного типа приводятся общие рекомендации для подготовки
к соревнованиям, касающиеся классификации заданий, анализа алгоритмов и пр.
Кроме стандартных тем (структуры данных и библиотеки, графы, математика,
вычислительная геометрия) авторы затрагивают и малораспространенные – им
посвящена отдельная глава.
В конце каждой главы приводятся краткие решения заданий, не помеченных
звездочкой, или даются подсказки к ним. Задания сложного уровня (помеченные
звездочкой) требуют самостоятельной проработки.
Издание адресовано читателям, которые готовятся к соревнованиям по про­
граммированию или просто любят решать задачи по информатике. Для изучения
материала требуются элементарные знания из области методологии програм­
мирования и знакомство хотя бы с одним из двух языков программирования –
C/C++ или Java.

УДК 004.02, 004.424
ББК 22.18

Russian­language edition copyright © 2020 by DMK Press. All rights reserved.
Все права защищены. Любая часть этой книги не может быть воспроизведена в ка­
кой бы то ни было форме и какими бы то ни было средствами без письменного разрешения
владельцев авторских прав.

ISBN 978­5­97060­758­9 (рус.)

© Steven Halim, Felix Halim, 2013
© Оформление, издание, перевод,
ДМК Пресс, 2020

Содержание
Вступление ................................................................................................................... 11
Предисловие ............................................................................................................... 13
От издательства ......................................................................................................... 27
Об авторах этой книги .......................................................................................... 28
Список сокращений ................................................................................................ 30
Глава 1. Введение ..................................................................................................... 32
1.1. Олимпиадное программирование....................................................................... 32
1.2. Как стать конкурентоспособным ......................................................................... 35
1.2.1. Совет 1: печатайте быстрее! .......................................................................... 36
1.2.2. Совет 2: быстро классифицируйте задачи ................................................. 37
1.2.3. Совет 3: проводите анализ алгоритмов ...................................................... 40
1.2.4. Совет 4: совершенствуйте свои знания языков
программирования .................................................................................................... 46
1.2.5. Совет 5: овладейте искусством тестирования кода ................................. 48
1.2.6. Совет 6: практикуйтесь и еще раз практикуйтесь! .................................. 52
1.2.7. Совет 7: организуйте командную работу (для ICPC) ............................... 53
1.3. Начинаем работу: простые задачи ...................................................................... 54
1.3.1. Общий анализ олимпиадной задачи по программированию .............. 54
1.3.2. Типичные процедуры ввода/вывода ........................................................... 55
1.3.3. Начинаем решать задачи ............................................................................... 57
1.4. Задачи Ad Hoc ........................................................................................................... 60
1.5. Решения упражнений, не помеченных звездочкой ........................................ 68
1.6. Примечания к главе 1.............................................................................................. 73

Глава 2. Структуры данных и библиотеки ................................................. 76
2.1. Общий обзор и мотивация ................................................................................... 76
2.2. Линейные структуры данных – встроенные библиотеки .............................. 79
2.3. Нелинейные структуры данных – встроенные библиотеки .......................... 90
2.4. Структуры данных с реализациями библиотек, написанными
авторами этой книги ...................................................................................................... 99
2.4.1. Граф ..................................................................................................................... 99
2.4.2. Система непересекающихся множеств......................................................103
2.4.3. Дерево отрезков...............................................................................................107
2.4.4. Дерево Фенвика ...............................................................................................112
2.5. Решения упражнений, не помеченных звездочкой .......................................118
2.6. --">