анти. Guide to Competitive
 Скачать 2.39 Mb.
|
|
Антти Лааксонен Олимпиадное программирование Изучение и улучшение алгоритмов на соревнованиях 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 |