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

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

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

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 с.: ил. 

ISBN978-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.

Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения 
владельцев авторских прав.

 
© Steven Halim, Felix Halim, 2013
ISBN 978­5­97060­758­9 (рус.) 
©  Оформление, издание, перевод, 
ДМК Пресс, 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. Примечания к главе 2 .............................................................................................121

 Содержание

Глава 3. Некоторые способы решения задач .........................................124
3.1. Общий обзор и мотивация ...................................................................................124
3.2. Полный перебор ......................................................................................................125
3.2.1. Итеративный полный перебор ....................................................................127
3.2.2. Рекурсивный полный перебор (возвратная рекурсия) ..........................130
3.2.3. Советы ................................................................................................................134
3.3. «Разделяй и властвуй» ...........................................................................................146
3.3.1. Интересное использование двоичного поиска ........................................146
3.4. «Жадные» алгоритмы ............................................................................................152
3.4.1. Примеры ............................................................................................................153
3.5. Динамическое программирование ....................................................................160
3.5.1. Примеры DP ......................................................................................................161
3.5.2. Классические примеры ..................................................................................171
3.5.3. Неклассические примеры .............................................................................184
3.6. Решения упражнений, не помеченных звездочкой .......................................192
3.7. Примечания к главе 3 .............................................................................................195

Глава 4. Графы ...........................................................................................................197
4.1. Общий обзор и мотивация ...................................................................................197
4.2. Обход графа ..............................................................................................................198
4.2.1. Поиск в глубину (Depth First Search, DFS) ..................................................198
4.2.2. Поиск в ширину (Breadth First Search, BFS) ...............................................200
4.2.3. Поиск компонент связности (неориентированный граф) ....................202
4.2.4. Закрашивание – Маркировка/раскрашивание компонент  
связности .....................................................................................................................203
4.2.5. Топологическая сортировка (направленный ациклический граф) ....204
4.2.6. Проверка двудольности графа .....................................................................206
4.2.7. Проверка свойств ребер графа через остовное дерево DFS ..................207
4.2.8. Нахождение точек сочленения и мостов (неориентированный  
граф) ..............................................................................................................................209
4.2.9. Нахождение компонент сильной связности (ориентированный  
граф) ..............................................................................................................................212
4.3. Минимальное остовное дерево ...........................................................................218
4.3.1. Обзор ..................................................................................................................218
4.3.2. Алгоритм Краскала .........................................................................................219
4.3.3. Алгоритм Прима ..............................................................................................221
4.3.4. Другие варианты применения .....................................................................222
4.4. Нахождение кратчайших путей из заданной вершины во все  
остальные (Single – Source Shortest Paths, SSSP) .....................................................229
4.4.1. Обзор ..................................................................................................................229
4.4.2. SSSP на невзвешенном графе .......................................................................230
4.4.3. SSSP на взвешенном графе ...........................................................................232
4.4.4. SSSP на графе, имеющем цикл с отрицательным весом .......................237
4.5. Кратчайшие пути между всеми вершинами ....................................................242
4.5.1. Обзор ..................................................................................................................242
4.5.2. Объяснение алгоритма DP Флойда–Уоршелла .........................................243
4.5.3. Другие применения ........................................................................................246

Содержание  7

4.6. Поток ..........................................................................................................................253
4.6.1. Обзор ..................................................................................................................253
4.6.2. Метод Форда–Фалкерсона ............................................................................254
4.6.3. Алгоритм Эдмондса–Карпа ..........................................................................256
4.6.4. Моделирование графа потока – часть I ......................................................257
4.6.5. Другие разновидности задач, использующих поток ..............................259
4.6.6. Моделирование графа потока – часть II ....................................................261
4.7. Специальные графы ...............................................................................................264
4.7.1. Направленный ациклический граф ............................................................265
4.7.2. Дерево .................................................................................................................274
4.7.3. Эйлеров граф ....................................................................................................276
4.7.4. Двудольный граф .................................................................................................277
4.8. Решения упражнений, не помеченных звездочкой .......................................287
4.9. Примечания к главе 4 .............................................................................................291

Глаа 5. Математика .................................................................................................293
5.1. Общий обзор и мотивация ...................................................................................293
5.2. Задачи Ad Hoc и математика ................................................................................294
5.3. Класс Java BigInteger ...............................................................................................303
5.3.1. Основные функции .........................................................................................303
5.3.2. Дополнительные функции  ...........................................................................305
5.4. Комбинаторика ........................................................................................................311
5.4.1. Числа Фибоначчи ............................................................................................311
5.4.2. Биномиальные коэффициенты ...................................................................312
5.4.3. Числа Каталана ................................................................................................313
5.5. Теория чисел .............................................................................................................319
5.5.1. Простые числа ..................................................................................................319
5.5.2. Наибольший общий делитель и наименьшее общее кратное ..............322
5.5.3. Факториал .........................................................................................................322
5.5.4. Нахождение простых множителей с помощью  
оптимизированных операций пробных разложений на множители ...........323
5.5.5. Работа с простыми множителями ...............................................................324
5.5.6. Функции, использующие простые множители ........................................325
5.5.7. Модифицированное «решето» .....................................................................327
5.5.8. Арифметические операции по модулю .....................................................327
5.5.9. Расширенный алгоритм Евклида:  
решение линейного диофантова уравнения ......................................................328
5.6. Теория вероятностей ..............................................................................................334
5.7. Поиск цикла ..............................................................................................................336
5.7.1. Решение(я), использующее(ие) эффективные структуры данных ......337
5.7.2. Алгоритм поиска цикла, реализованный Флойдом ................................337
5.8. Теория игр .................................................................................................................340
5.8.1. Дерево решений ..............................................................................................341
5.8.2. Знание математики и ускорение решения ...............................................342
5.8.3. Игра Ним ...........................................................................................................343
5.9. Решения упражнений, не помеченных звездочкой .......................................344
5.10. Примечания к главе 5 ..........................................................................................346

 Содержание

Глава 6. Обработка строк ....................................................................................349
6.1. Обзор и мотивация .................................................................................................349
6.2. Основные приемы и принципы обработки строк ..........................................350
6.3. Специализированные задачи обработки строк ..............................................353
6.4. Поиск совпадений в строках ................................................................................360
6.4.1. Решения с использованием библиотечных функций ............................361
6.4.2. Алгоритм Кнута–Морриса–Пратта .............................................................361
6.4.3. Поиск совпадений в строках на двумерной сетке ...................................364
6.5. Обработка строк с применением динамического программирования .....366
6.5.1. Регулирование строк (редакционное расстояние) ..................................366
6.5.2. Поиск наибольшей общей подпоследовательности ...............................369
6.5.3. Неклассические задачи обработки строк с применением  
динамического программирования......................................................................370
6.6. Суффиксный бор, суффиксное дерево, суффиксный массив .......................372
6.6.1. Суффиксный бор и его приложения ...........................................................372
6.6.2. Суффиксное дерево .........................................................................................374
6.6.3. Практические приложения суффиксного дерева ....................................375
6.6.4. Суффиксный массив .......................................................................................379
6.6.5. Практические приложения суффиксного массива .................................386
6.7. Решения упражнений, не помеченных звездочкой ........................................392
6.8. Примечания к главе ................................................................................................396

Глава 7. (Вычислительная) Геометрия ........................................................398
7.1. Обзор и мотивация .................................................................................................398
7.2. Основные геометрические объекты и библиотечные функции для них ...400
7.2.1. Нульмерные объекты: точки .........................................................................400
7.2.2. Одномерные объекты: прямые ....................................................................403
7.2.3. Двумерные объекты: окружности ...............................................................408
7.2.4. Двумерные объекты: треугольники ............................................................411
7.2.5. Двумерные объекты: четырехугольники ...................................................414
7.2.6. Замечания о трехмерных объектах .............................................................415
7.3. Алгоритмы для многоугольников с использованием библиотечных  
функций ............................................................................................................................418
7.3.1. Представление многоугольника ..................................................................419
7.3.2. Периметр многоугольника ............................................................................419
7.3.3. Площадь многоугольника ..............................................................................420
7.3.4. Проверка многоугольника на выпуклость ................................................420
7.3.5. Проверка расположения точки внутри многоугольника .......................421
7.3.6. Разделение многоугольника с помощью прямой линии .......................422
7.3.7. Построение выпуклой оболочки множества точек ..................................424
7.4. Решения упражнений, не помеченных звездочкой ........................................430
7.5. Замечания к главе ...................................................................................................434

Глава 8. Более сложные темы .........................................................................436
8.1. Обзор и мотивация .................................................................................................436
8.2. Более эффективные методы поиска ...................................................................436

Содержание  9

8.2.1. Метод поиска с возвратами с применением битовой маски ...............437
8.2.2. Поиск с возвратами с интенсивным отсечением ....................................442
8.2.3. Поиск в пространстве состояний с применением поиска  
в ширину или алгоритма Дейкстры ......................................................................444
8.2.4. Встреча в середине (двунаправленный поиск) ........................................446
8.2.5. Поиск, основанный на имеющейся информации: A* и IDA* ................448
8.3. Более эффективные методы динамического программирования .............455
8.3.1. Динамическое программирование с использованием битовой  
маски .............................................................................................................................455
8.3.2. Некоторые общие параметры (динамического  
программирования) ..................................................................................................456
8.3.3. Обработка отрицательных значений параметров  
с использованием метода смещения ....................................................................458
8.3.4. Превышение лимита памяти? Рассмотрим использование  
сбалансированного бинарного дерева поиска как таблицы  
запоминания состояний ..........................................................................................460
8.3.5. Превышение лимита памяти/времени? Используйте более  
эффективное представление состояния ..............................................................460
8.3.6. Превышение лимита памяти/времени? Отбросим один параметр, 
будем восстанавливать его по другим параметрам ..........................................462
8.4. Декомпозиция задачи ............................................................................................467
8.4.1. Два компонента: бинарный поиск ответа и прочие ..............................468
8.4.2. Два компонента: использование статической задачи RSQ/RMQ ........470
8.4.3. Два компонента: предварительная обработка графа  
и динамическое программирование ....................................................................471
8.4.4. Два компонента: использование графов ..................................................473
8.4.5. Два компонента: использование математики .........................................474
8.4.6. Два компонента: полный поиск и геометрия ..........................................474
8.4.7. Два компонента: использование эффективной структуры данных ...474
8.4.8. Три компонента ...............................................................................................475
8.5. Решения упражнений, не помеченных звездочкой .......................................484
8.6. Замечания к главе ...................................................................................................485

Глава 9. Малораспространенные темы ......................................................487
Общий обзор и мотивация ...........................................................................................487
9.1. Задача 2­SAT .............................................................................................................488
9.2. Задача о картинной галерее .................................................................................491
9.3. Битоническая задача коммивояжера .................................................................492
9.4. Разбиение скобок на пары ....................................................................................495
9.5. Задача китайского почтальона ............................................................................496
9.6. Задача о паре ближайших точек ..........................................................................497
9.7. Алгоритм Диница ....................................................................................................499
9.8. Формулы или теоремы...........................................................................................500
9.9. Алгоритм последовательного исключения переменных, или метод  
Гаусса .................................................................................................................................502
9.10. Паросочетание в графах ......................................................................................505
9.11. Кратчайшее расстояние на сфере (ортодромия) ...........................................509

 Содержание

9.12. Алгоритм Хопкрофта–Карпа..............................................................................511
9.13. Вершинно и реберно не пересекающиеся пути ............................................512
9.14. Количество инверсий ...........................................................................................513
9.15. Задача Иосифа Флавия ........................................................................................515
9.16. Ход коня ..................................................................................................................516
9.17. Алгоритм Косараджу ............................................................................................518
9.18. Наименьший общий предок ..............................................................................519
9.19. Создание магических квадратов (нечетной размерности) ........................522
9.20. Задача о порядке умножения матриц ..............................................................523
9.21. Возведение матрицы в степень .........................................................................525
9.22. Задача о независимом множестве максимального веса .............................530
9.23. Максимальный поток минимальной стоимости ..........................................532
9.24. Минимальное покрытие путями в ориентированном  
ациклическом графе ......................................................................................................533
9.25. Блинная сортировка .............................................................................................535
9.26. Ро­алгоритм Полларда для разложения на множители целых чисел ......538
9.27. Постфиксный калькулятор и преобразование выражений ........................540
9.28. Римские цифры .....................................................................................................543
9.29. k­я порядковая статистика .................................................................................545
9.30. Алгоритм ускоренного поиска кратчайшего пути .......................................549
9.31. Метод скользящего окна .....................................................................................550
9.32. Алгоритм сортировки с линейным временем работы.................................553
9.33. Структура данных «разреженная таблица» ....................................................555
9.34. Задача о ханойских башнях................................................................................558
9.35. Замечания к главе .................................................................................................559

Приложение А. uHunt ............................................................................................562

Приложение В. Благодарности .......................................................................567

Список используемой литературы ...............................................................569

Предметный указатель ........................................................................................574