Олимпиадное программирование. Изучение и улучшение алгоритмов на соревнованиях (5000,00 руб.)

Стр.5

Стр.6

Стр.7

Стр.8

Стр.9

Стр.10

Стр.11

УДК 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 (англ.) ISBN 978-5-97060-878-4 (рус.) © Springer Nature Switzerland AG, 2020 © Оформление, перевод на русский язык, издание, ДМК Пресс, 2020

Стр.5

Оглавление От автора .......................................................................................................................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

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

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

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

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

Стр.11