УДК 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
Russianlanguage edition copyright © 2020 by DMK Press. All rights reserved.
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой
бы то ни было форме и какими бы то ни было средствами без письменного разрешения
владельцев авторских прав.
ISBN 9785970607589 (рус.)
© Steven Halim, Felix Halim, 2013
© Оформление, издание, перевод,
ДМК Пресс, 2020
Стр.5
Содержание
Вступление ................................................................................................................... 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
Стр.6
6 Содержание
Глава 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
Содержание 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
Стр.8
8 Содержание
Глава 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
Содержание 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. Задача 2SAT .............................................................................................................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
Стр.10
10 Содержание
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
Стр.11