Олимпиадное программирование: изучение и улучшение алгоритмов на соревнованиях

Антти Лааксонен

Олимпиадное 
программирование

Изучение и улучшение алгоритмов 
на соревнованиях

2-е издание, обновленное и дополненное

Guide to Competitive 
Programming

Learning and Improving Algorithms  
Through Contests

Second Edition 

Antti Laaksonen

Москва, 2020

Олимпиадное 
программирование

Изучение и улучшение алгоритмов 
на соревнованиях

2-е издание, обновленное и дополненное 

Антти Лааксонен

УДК   004.02: 004.424
ББК    22.18
Л12

Л12  Антти Лааксонен
Олимпиадное программирование. 2-е изд., обновленное и дополненное / пер. с англ. А. А. Слинкин – М.: ДМК Пресс, 2020. – 328 с.: ил.

            ISBN  978-5-97060-878-4

Перед вами второе, обновленное издание книги, которая уже успела полюбиться читателям. Автор подробно описывает, как проходят олимпиады по 
программированию и как к ним готовиться, разбирает базовые темы, трюки и 
алгоритмы. В новых разделах рассматриваются темы повышенного уровня: вычисление преобразования Фурье, нахождение потоков минимальной стоимости 
в графах и использование конечных автоматов в задачах о строках.
Спортивное программирование – самый перспективный интеллектуальный 
вид спорта; уже сейчас им увлекаются лучшие умы планеты, и число участников растет год от года. Рост популярности олимпиадного программирования 
положительно влияет на другие сферы жизнедеятельности человека. Навыки 
быстрого решения сложнейших задач помогут сегодняшним студентам в будущем эффективно справляться с реальными проблемами человечества.
Издание будет полезно студентам факультетов информационных технологий 
и участникам олимпиад по программированию.

УДК  004.02: 004.424
 
 
 
 
 
 
 
 
ББК  22.18

Original English language edition published by Springer International Publishing 
AG. Copyright ©Springer International Publishing AG, part of Springer Nature 2020. All 
rights reserved. This edition has been translated and published under licence from Springer 
International Publishing AG. Russian-language edition copyright © 2020 by DMK Press. All 
rights reserved. 

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

ISBN 978-3-030-39357-1 (англ.)                         © Springer Nature Switzerland AG, 2020 
ISBN  978-5-97060-878-4 (рус.)                         © Оформление, перевод на русский язык, 
 
 
    издание, ДМК Пресс, 2020

Оглавление

От автора .......................................................................................................................11
Вступительное слово Алексея Малеева, основателя Moscow Workshops ............. 11
Отзыв Дмитрия Гришина, основателя Mail.Ru Group .............................................13
Благодарность от редакции .......................................................................................13
Отзыв Нияза Нигматуллина, двукратного чемпиона мира  
ACM ICPC 2012 и 2013 годов .....................................................................................14
Предисловие ко второму изданию ...........................................................................15
Предисловие к первому изданию .............................................................................16
Глава 1. Введение .........................................................................................................18

1.1. Что такое олимпиадное программирование? .................................................... 18

1.1.1. Соревнования по программированию .....................................................................19
1.1.2. Рекомендации желающим поучаствовать ...............................................................20

1.2. Об этой книге ................................................................................................................... 20
1.3. Сборник задач CSES ...................................................................................................... 22
1.4. Другие ресурсы ............................................................................................................... 24

Глава 2. Техника программирования ........................................................................26

2.1. Языковые средства ........................................................................................................ 26

2.1.1. Ввод и вывод .......................................................................................................................27
2.1.2. Работа с числами ...............................................................................................................28
2.1.3. Сокращение кода ..............................................................................................................31

2.2. Рекурсивные алгоритмы .............................................................................................. 32

2.2.1. Порождение подмножеств ............................................................................................32
2.2.2. Порождение перестановок ...........................................................................................33
2.2.3. Перебор с возвратом .......................................................................................................34

2.3. Поразрядные операции ............................................................................................... 36

2.3.1. Поразрядные операции ..................................................................................................38
2.3.2. Представление множеств ..............................................................................................40

Глава 3. Эффективность ..............................................................................................43

3.1. Временная сложность ................................................................................................... 43

3.1.1. Правила вычисления .......................................................................................................43
3.1.2. Часто встречающиеся оценки временной сложности .......................................46
3.1.3. Оценка эффективности ...................................................................................................47
3.1.4. Формальные определения ............................................................................................48

3.2. Примеры проектирования алгоритмов ................................................................. 49

3.2.1. Максимальная сумма подмассивов ...........................................................................49
3.2.2. Задача о двух ферзях ......................................................................................................51

3.3. Оптимизация кода .......................................................................................................... 53

3.3.1. Результат работы компилятора....................................................................................54

 Оглавление

3.3.2. Особенности процессора ...............................................................................................56

Глава 4. Сортировка и поиск.......................................................................................59

4.1. Алгоритмы сортировки ................................................................................................. 59

4.1.1. Пузырьковая сортировка ...............................................................................................60
4.1.2. Сортировка слиянием ......................................................................................................61
4.1.3. Нижняя граница временной сложности сортировки .........................................62
4.1.4. Сортировка подсчетом ....................................................................................................63
4.1.5. Сортировка на практике .................................................................................................63

4.2. Решение задач с применением сортировки ....................................................... 66

4.2.1. Алгоритмы заметающей прямой .................................................................................66
4.2.2. Составление расписания ................................................................................................67
4.2.3. Работы и сроки исполнения .........................................................................................68

4.3. Двоичный поиск .............................................................................................................. 69

4.3.1. Реализация поиска ...........................................................................................................69
4.3.2. Двоичный поиск по ответу ............................................................................................71

Глава 5. Структуры данных .........................................................................................74

5.1. Динамические массивы ............................................................................................... 74

5.1.1. Векторы .................................................................................................................................74
5.1.2. Итераторы и диапазоны .................................................................................................75
5.1.3. Другие структуры данных ..............................................................................................77

5.2. Множества ......................................................................................................................... 78

5.2.1. Множества и мультимножества ...................................................................................78
5.2.2. Отображения .......................................................................................................................80
5.2.3. Очереди с приоритетом .................................................................................................81
5.2.4. Множества, основанные на политиках .....................................................................82

5.3. Эксперименты .................................................................................................................. 83

5.3.1. Сравнение множества и сортировки.........................................................................83
5.3.2. Сравнение отображения и массива...........................................................................84
5.3.3. Сравнение очереди с приоритетом и мультимножества ..................................84

Глава 6. Динамическое программирование ............................................................86

6.1. Основные понятия ......................................................................................................... 86

6.1.1. Когда жадный алгоритм не работает ........................................................................86
6.1.2. Нахождение оптимального решения ........................................................................87
6.1.3. Подсчет решений ..............................................................................................................91

6.2. Другие примеры .............................................................................................................. 92

6.2.1. Наибольшая возрастающая подпоследовательность .........................................92
6.2.2. Пути на сетке .......................................................................................................................93
6.2.3. Задачи о рюкзаке ..............................................................................................................95
6.2.4. От перестановок к подмножествам ...........................................................................97
6.2.5. Подсчет количества замощений .................................................................................98

Глава 7. Алгоритмы на графах ..................................................................................101

7.1. Основы теории графов ...............................................................................................101

7.1.1.Терминология .................................................................................................................... 102

Оглавление  7

7.1.2. Представление графа.................................................................................................... 104

7.2. Обход графа ....................................................................................................................107

7.2.1. Поиск в глубину ................................................................................................................107
7.2.2. Поиск в ширину ............................................................................................................... 109
7.2.3. Применения ...................................................................................................................... 110

7.3. Кратчайшие пути ...........................................................................................................111

7.3.1. Алгоритм Беллмана–Форда ....................................................................................... 112
7.3.2. Алгоритм Дейкстры ........................................................................................................ 114
7.3.3. Алгоритм Флойда–Уоршелла ..................................................................................... 116

7.4. Ориентированные ациклические графы .............................................................118

7.4.1. Топологическая сортировка ....................................................................................... 119
7.4.2. Динамическое программирование ......................................................................... 120

7.5. Графы преемников........................................................................................................122

7.5.1. Нахождение преемников ............................................................................................ 123
7.5.2. Обнаружение циклов .................................................................................................... 124

7.6. Минимальные остовные деревья ...........................................................................125

7.6.1. Алгоритм Краскала ......................................................................................................... 126
7.6.2. Система непересекающихся множеств.................................................................. 128
7.6.3. Алгоритм Прима .............................................................................................................. 130

Глава 8. Избранные вопросы проектирования алгоритмов ...............................132

8.1. Алгоритмы с параллельным просмотром разрядов .......................................132

8.1.1. Расстояние Хэмминга ................................................................................................... 132
8.1.2. Подсчет подсеток ........................................................................................................... 134
8.1.3. Достижимость в графах ............................................................................................... 135

8.2. Амортизационный анализ .........................................................................................136

8.2.1. Метод двух указателей ................................................................................................ 136
8.2.2. Ближайшие меньшие элементы ............................................................................... 138
8.2.3. Минимум в скользящем окне .................................................................................... 139

8.3. Нахождение минимальных значений ..................................................................140

8.3.1. Тернарный поиск ............................................................................................................ 141
8.3.2. Выпуклые функции ........................................................................................................ 142
8.3.3. Минимизация сумм ....................................................................................................... 142

Глава 9. Запросы по диапазону................................................................................144

9.1. Запросы к статическим массивам .........................................................................144

9.1.1. Запросы о сумме ............................................................................................................ 144
9.1.2. Запросы о минимуме .................................................................................................... 146

9.2. Древовидные структуры ............................................................................................147

9.2.1. Двоичные индексные деревья...................................................................................147
9.2.2. Деревья отрезков ........................................................................................................... 150
9.2.3. Дополнительные приемы ............................................................................................ 154

Глава 10. Алгоритмы на деревьях ...........................................................................157

10.1. Базовые понятия ........................................................................................................157

10.1.1. Обход дерева ................................................................................................................ 158

 Оглавление

10.1.2. Вычисление диаметра ............................................................................................... 159
10.1.3. Все максимальные пути ............................................................................................ 161

10.2. Запросы к деревьям .................................................................................................162

10.2.1. Нахождение предков ................................................................................................. 162
10.2.2. Поддеревья и пути ...................................................................................................... 163
10.2.3. Наименьшие общие предки .................................................................................... 165
10.2.4. Объединение структур данных .............................................................................. 168

10.3. Более сложные приемы ...........................................................................................169

10.3.1. Центроидная декомпозиция ................................................................................... 170
10.3.2. Heavy-light декомпозиция ....................................................................................... 170

Глава 11. Математика ................................................................................................172

11.1. Теория чисел.................................................................................................................172

11.1.1. Простые числа и разложение на простые множители ................................. 172
11.1.2. Решето Эратосфена  ................................................................................................... 175
11.1.3. Алгоритм Евклида ........................................................................................................ 176
11.1.4. Возведение в степень по модулю ......................................................................... 178
11.1.5. Теорема Эйлера ............................................................................................................ 178
11.1.6. Решение уравнений в целых числах ................................................................... 180

11.2. Комбинаторика ...........................................................................................................181

11.2.1. Биномиальные коэффициенты .............................................................................. 181
11.2.2. Числа Каталана ............................................................................................................. 184
11.2.3. Включение-исключение ........................................................................................... 186
11.2.4. Лемма Бёрнсайда ........................................................................................................ 188
11.2.5. Теорема Кэли ................................................................................................................. 189

11.3. Матрицы .........................................................................................................................190

11.3.1. Операции над матрицами ........................................................................................ 190
11.3.2. Линейные рекуррентные соотношения.............................................................. 192
11.3.3. Графы и матрицы ......................................................................................................... 194
11.3.4. Метод Гаусса .................................................................................................................. 196

11.4. Вероятность ..................................................................................................................199

11.4.1. Операции с событиями ............................................................................................. 200
11.4.2. Случайные величины.................................................................................................. 201
11.4.3. Марковские цепи ......................................................................................................... 203
11.4.4. Рандомизированные алгоритмы ........................................................................... 205

11.5. Теория игр .....................................................................................................................207

11.5.1. Состояния игры ..............................................................................................................207
11.5.2. Игра ним .......................................................................................................................... 209
11.5.3. Теорема Шпрага–Гранди .......................................................................................... 210

11.6. Преобразование Фурье ...........................................................................................213

11.6.1. Работа с полиномами ................................................................................................. 213
11.6.2. Алгоритм БПФ ............................................................................................................... 214
11.6.3. Вычисление свертки ....................................................................................................217

Глава 12. Дополнительные алгоритмы на графах ................................................219

12.1. Сильная связность......................................................................................................219

Оглавление  9

12.1.1. Алгоритм Косарайю .................................................................................................... 220
12.1.2. Задача 2-выполнимости ........................................................................................... 221

12.2. Полные пути .................................................................................................................223

12.2.1. Эйлеровы пути .............................................................................................................. 223
12.2.2. Гамильтоновы пути ...................................................................................................... 226
12.2.3. Применения ................................................................................................................... 226

12.3. Максимальные потоки .............................................................................................228

12.3.1. Алгоритм Форда–Фалкерсона  .............................................................................. 229
12.3.2. Непересекающиеся пути .......................................................................................... 232
12.3.3. Максимальные паросочетания .............................................................................. 233
12.3.4. Покрытие путями ......................................................................................................... 235

12.4. Деревья поиска в глубину ......................................................................................237

12.4.1. Двусвязность .................................................................................................................. 238
12.4.2. Эйлеровы подграфы ................................................................................................... 239

12.5. Потоки минимальной стоимости .........................................................................240

12.5.1. Алгоритм путей минимальной стоимости .......................................................... 241
12.5.2. Паросочетания минимального веса ..................................................................... 243
12.5.3. Улучшение алгоритма ................................................................................................ 244

Глава 13. Геометрия ...................................................................................................247

13.1. Технические средства в геометрии ....................................................................247

13.1.1. Комплексные числа .....................................................................................................247
13.1.2. Точки и прямые ............................................................................................................. 249
13.1.3. Площадь многоугольника ......................................................................................... 252
13.1.4. Метрики ........................................................................................................................... 254

13.2. Алгоритмы на основе заметающей прямой ....................................................256

13.2.1. Точки пересечения ...................................................................................................... 256
13.2.2. Задача о ближайшей паре точек ............................................................................257
13.2.3. Задача о выпуклой оболочке ................................................................................. 258

Глава 14. Алгоритмы работы со строками .............................................................260

14.1. Базовые методы .........................................................................................................260

14.1.1. Префиксное дерево .................................................................................................... 261
14.1.2. Динамическое программирование ...................................................................... 261

14.2. Хеширование строк ...................................................................................................263

14.2.1. Полиномиальное хеширование ............................................................................. 263
14.2.2. Применения ................................................................................................................... 263
14.2.3. Коллизии и параметры .............................................................................................. 264

14.3. Z-алгоритм .....................................................................................................................266

14.3.1. Построение Z-массива ............................................................................................... 266
14.3.2. Применения ................................................................................................................... 268

14.4. Суффиксные массивы ...............................................................................................269

14.4.1. Метод удвоения префикса ....................................................................................... 269
14.4.2. Поиск образцов ............................................................................................................ 270
14.4.3. LCP-массивы .................................................................................................................. 271

 Оглавление

14.5. Строковые автоматы .................................................................................................272

14.5.1. Регулярные языки ........................................................................................................ 273
14.5.2. Автоматы для сопоставления с образцом ......................................................... 274
14.5.3. Суффиксные автоматы .............................................................................................. 276

Глава 15. Дополнительные темы .............................................................................279

15.1. Квадратный корень в алгоритмах .......................................................................279

15.1.1. Структуры данных ........................................................................................................ 279
15.1.2. Подалгоритмы ............................................................................................................... 281
15.1.3. Целые разбиения ......................................................................................................... 283
15.1.4. Алгоритм Мо .................................................................................................................. 285

15.2. И снова о деревьях отрезков ................................................................................286

15.2.1. Ленивое распространение ........................................................................................287
15.2.2. Динамические деревья ............................................................................................. 290
15.2.3. Структуры данных в вершинах .............................................................................. 292
15.2.4. Двумерные деревья .................................................................................................... 293

15.3. Дучи .................................................................................................................................294

15.3.1. Разбиение и слияние ................................................................................................. 295
15.3.2. Реализация ..................................................................................................................... 296
15.3.3. Дополнительные методы .......................................................................................... 298

15.4. Оптимизация динамического программирования .......................................298

15.4.1. Трюк с выпуклой оболочкой ................................................................................... 299
15.4.2. Оптимизация методом «разделяй и властвуй» ............................................... 301
15.4.3. Оптимизация Кнута..................................................................................................... 302

15.5. Методы перебора с возвратом ............................................................................303

15.5.1. Отсечение ветвей дерева поиска ......................................................................... 304
15.5.2. Эвристические функции............................................................................................ 306

15.6. Разное .............................................................................................................................308

15.6.1. Встреча в середине ..................................................................................................... 308
15.6.2. Подсчет подмножеств ................................................................................................ 309
15.6.3. Параллельный двоичный поиск ............................................................................ 310
15.6.4. Динамическая связность ........................................................................................... 312

Приложение. Сведения из математики ..................................................................315

Формулы сумм .......................................................................................................................315
Множества ...............................................................................................................................317
Математическая логика .....................................................................................................318
Функции ....................................................................................................................................319
Логарифмы ..............................................................................................................................319
Системы счисления ..............................................................................................................320

Библиография ............................................................................................................321
Предметный указатель .............................................................................................323