Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

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

Изучение и улучшение алгоритмов на соревнованиях
Покупка
Новинка
Артикул: 746441.05.99
Доступ онлайн
899 ₽
В корзину
Перед вами второе, обновленное издание книги, которая уже успела полюбиться читателям. Автор подробно описывает, как проходят олимпиады по программированию и как к ним готовиться, разбирает базовые темы, трюки и алгоритмы. В новых разделах рассматриваются темы повышенного уровня: вычисление преобразования Фурье, нахождение потоков минимальной стоимости в графах и использование конечных автоматов в задачах о строках. Спортивное программирование — самый перспективный интеллектуальный вид спорта; уже сейчас им увлекаются лучшие умы планеты, и число участников растет год от года. Рост популярности олимпиадного программирования положительно влияет на другие сферы жизнедеятельности человека. Навыки быстрого решения сложнейших задач помогут сегодняшним студентам в будущем эффективно справляться с реальными проблемами человечества. Издание будет полезно студентам факультетов информационных технологий и участникам олимпиад по программированию.
172
279
Лааксонен, А. Олимпиадное программирование : изучение и улучшение алгоритмов на соревнованиях : учебное пособие / А. Лааксонен ; пер. с англ. А. А. Слинкин. – 2-е изд., обновл. и доп. - Москва : ДМК Пресс, 2020. - 330 с. – ISBN 978-5-97060-878-4. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2261619 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Антти Лааксонен
Олимпиадное 
программирование
Изучение и улучшение алгоритмов 
на соревнованиях
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


6    Оглавление
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


8    Оглавление
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


10    Оглавление
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


Доступ онлайн
899 ₽
В корзину