Олимпиадное программирование
Изучение и улучшение алгоритмов на соревнованиях
Покупка
Новинка
Тематика:
Программирование и алгоритмизация
Издательство:
ДМК Пресс
Автор:
Лааксонен Антти
Перевод:
Слинкин Алексей Александрович
Год издания: 2020
Кол-во страниц: 330
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-97060-878-4
Артикул: 746441.05.99
Перед вами второе, обновленное издание книги, которая уже успела полюбиться читателям. Автор подробно описывает, как проходят олимпиады по программированию и как к ним готовиться, разбирает базовые темы, трюки и алгоритмы. В новых разделах рассматриваются темы повышенного уровня: вычисление преобразования Фурье, нахождение потоков минимальной стоимости в графах и использование конечных автоматов в задачах о строках.
Спортивное программирование — самый перспективный интеллектуальный вид спорта; уже сейчас им увлекаются лучшие умы планеты, и число участников растет год от года. Рост популярности олимпиадного программирования положительно влияет на другие сферы жизнедеятельности человека. Навыки быстрого решения сложнейших задач помогут сегодняшним студентам в будущем эффективно справляться с реальными проблемами человечества.
Издание будет полезно студентам факультетов информационных технологий и участникам олимпиад по программированию.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 09.03.01: Информатика и вычислительная техника
- 09.03.02: Информационные системы и технологии
- 09.03.03: Прикладная информатика
- 09.03.04: Программная инженерия
- ВО - Магистратура
- 09.04.01: Информатика и вычислительная техника
- 09.04.02: Информационные системы и технологии
- 09.04.03: Прикладная информатика
- 09.04.04: Программная инженерия
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Антти Лааксонен Олимпиадное программирование Изучение и улучшение алгоритмов на соревнованиях 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