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

Description

Пер. с англ. А. А. Слинкин. Эта книга помогает познакомиться с олимпиадным программированием. Она подробно описывает, как проходят олимпиады, что требуется от участника, в чем их цель, как к ним готовиться. Подробно разобраны базовые темы, трюки и алгоритмы. Спортивное программирование – это самый перспективный интеллектуаль­ный вид спорта, который можно назвать шахматами будущего. Уже сейчас им увлекаются лучшие умы планеты, и число участников растет год от года. Рост популярности олимпиадного программирования положительно влияет на другие сферы жизнедеятельности человека. Навыки быстрого решения сложнейших задач помогают сегодняшним студентам в будущем эффективно справляться с реальными проблемами человечества. Издание будет полезно прежде всего студентам, начинающим принимать участие в соревнованиях по программированию. Олимпиадное программирование_обложка Олимпиадное программирование_165_235_макет От автора Вступительное слово Алексея Малеева, основателя Moscow Workshops ICPC Отзыв Дмитрия Гришина, основателя Mail.Ru Group Благодарность от редакции Отзыв Нияза Нигматуллина, двукратного чемпиона мира ACM ICPC 2012 и 2013 годов Предисловие Глава 1 Введение 1.1. Что такое олимпиадное программирование? 1.1.1. Соревнования по программированию 1.1.2. Рекомендации желающим поучаствовать 1.2. Об этой книге 1.3. Сборник задач CSES 1.4. Другие ресурсы Глава 2 Техника программирования 2.1. Языковые средства 2.1.1. Ввод и вывод 2.1.2. Работа с числами 2.1.3. Сокращение кода 2.2. Рекурсивные алгоритмы 2.2.1. Порождение подмножеств 2.2.2. Порождение перестановок 2.2.3. Перебор с возвратом 2.3. Поразрядные операции 2.3.1. Поразрядные операции 2.3.2. Представление множеств Глава 3 Эффективность 3.1. Временная сложность 3.1.1. Правила вычисления 3.1.2. Часто встречающиеся оценки временной сложности 3.1.3. Оценка эффективности 3.1.4. Формальные определения 3.2. Примеры 3.2.1. Максимальная сумма подмассивов 3.2.2. Задача о двух ферзях Глава 4 Сортировка и поиск 4.1. Алгоритмы сортировки 4.1.1. Пузырьковая сортировка 4.1.2. Сортировка слиянием 4.1.3. Нижняя граница временной сложности сортировки 4.1.4. Сортировка подсчетом 4.1.5. Сортировка на практике 4.2. Решение задач с применением сортировки 4.2.1. Алгоритмы заметающей прямой 4.2.2. Составление расписания 4.2.3. Работы и сроки исполнения 4.3. Двоичный поиск 4.3.1. Реализация поиска 4.3.2. Нахождение оптимальных решений Глава 5 Структуры данных 5.1. Динамические массивы 5.1.1. Векторы 5.1.2. Итераторы и диапазоны 5.1.3. Другие структуры данных 5.2. Множества 5.2.1. Множества и мультимножества 5.2.2. Отображения 5.2.3. Очереди с приоритетом 5.2.4. Множества, основанные на политиках 5.3. Эксперименты 5.3.1. Сравнение множества и сортировки 5.3.2. Сравнение отображения и массива 5.3.3. Сравнение очереди с приоритетом и мультимножества Глава 6 Динамическое программирование 6.1. Основные понятия 6.1.1. Когда жадный алгоритм не работает 6.1.2. Нахождение оптимального решения 6.1.3. Подсчет решений 6.2. Другие примеры 6.2.1. Наибольшая возрастающая подпоследовательность 6.2.2. Пути на сетке 6.2.3. Задачи о рюкзаке 6.2.4. От перестановок к подмножествам 6.2.5. Подсчет количества замощений Глава 7 Алгоритмы на графах 7.1. Основы теории графов 7.1.1.Терминология 7.1.2. Представление графа 7.2. Обход графа 7.2.1. Поиск в глубину 7.2.2. Поиск в ширину 7.2.3. Применения 7.3. Кратчайшие пути 7.3.1. Алгоритм Беллмана–Форда 7.3.2. Алгоритм Дейкстры 7.3.3. Алгоритм Флойда–Уоршелла 7.4. Ориентированные ациклические графы 7.4.1. Топологическая сортировка 7.4.2. Динамическое программирование 7.5. Графы преемников 7.5.1. Нахождение преемников 7.5.2. Обнаружение циклов 7.6. Минимальные остовные деревья 7.6.1. Алгоритм Краскала 7.6.2. Система непересекающихся множеств 7.6.3. Алгоритм Прима Глава 8 Избранные вопросы проектирования алгоритмов 8.1. Алгоритмы с параллельным просмотром разрядов 8.1.1. Расстояние Хэмминга 8.1.2. Подсчет подсеток 8.1.3. Достижимость в графах 8.2. Амортизационный анализ 8.2.1. Метод двух указателей 8.2.2. Ближайшие меньшие элементы 8.2.3. Минимум в скользящем окне 8.3. Нахождение минимальных значений 8.3.1. Троичный поиск 8.3.2. Выпуклые функции 8.3.3. Минимизация сумм Глава 9 Запросы по диапазону 9.1. Запросы к статическим массивам 9.1.1. Запросы о сумме 9.1.2. Запросы о минимуме 9.2. Древовидные структуры 9.2.1. Двоичные индексные деревья 9.2.2. Деревья отрезков 9.2.3. Дополнительные приемы Глава 10 Алгоритмы на деревьях 10.1. Базовые понятия 10.1.1. Обход дерева 10.1.2. Вычисление диаметра 10.1.3. Все максимальные пути 10.2. Запросы к деревьям 10.2.1. Нахождение предков 10.2.2. Поддеревья и пути 10.2.3. Наименьшие общие предки 10.2.4. Объединение структур данных 10.3. Более сложные приемы 10.3.1. Центроидная декомпозиция 10.3.2. Разновесная декомпозиция Глава 11 Математика 11.1. Теория чисел 11.1.1. Простые числа и разложение на простые множители 11.1.2. Решето Эратосфена 11.1.3. Алгоритм Евклида 11.1.4. Возведение в степень по модулю 11.1.5. Теорема Эйлера 11.1.6. Решение уравнений в целых числах 11.2. Комбинаторика 11.2.1. Биномиальные коэффициенты 11.2.2. Числа Каталана 11.2.3. Включение-исключение 11.2.4. Лемма Бёрнсайда 11.2.5. Теорема Кэли 11.3. Матрицы 11.3.1. Операции над матрицами 11.3.2. Линейные рекуррентные соотношения 11.3.3. Графы и матрицы 11.3.4. Метод исключения Гаусса 11.4. Вероятность 11.4.1. Операции с событиями 11.4.2. Случайные величины 11.4.3. Марковские цепи 11.4.4. Рандомизированные алгоритмы 11.5. Теория игр 11.5.1. Состояния игры 11.5.2. Игра ним 11.5.3. Теорема Шпрага–Гранди Глава 12 Дополнительные алгоритмы на графах 12.1. Сильная связность 12.1.1. Алгоритм Косарайю 12.1.2. Задача 2-выполнимости 12.2. Полные пути 12.2.1. Эйлеровы пути 12.2.2. Гамильтоновы пути 12.2.3. Применения 12.3. Максимальные потоки 12.3.1. Алгоритм Форда–Фалкерсона 12.3.2. Непересекающиеся пути 12.3.3. Максимальные паросочетания 12.3.4. Покрытие путями 12.4. Деревья поиска в глубину 12.4.1. Двусвязность 12.4.2. Эйлеровы подграфы Глава 13 Геометрия 13.1. Технические средства в геометрии 13.1.1. Комплексные числа 13.1.2. Точки и прямые 13.1.3. Площадь многоугольника 13.1.4. Метрики 13.2. Алгоритмы на основе заметающей прямой 13.2.1. Точки пересечения 13.2.2. Задача о ближайшей паре точек 13.2.3. Задача о выпуклой оболочке Глава 14 Алгоритмы работы со строками 14.1. Базовые методы 14.1.1. Префиксное дерево 14.1.2. Динамическое программирование 14.2. Хеширование строк 14.2.1. Полиномиальное хеширование 14.2.2. Применения 14.2.3. Коллизии и параметры 14.3. Z-алгоритм 14.3.1. Построение Z-массива 14.3.2. Применения 14.4. Суффиксные массивы 14.4.1. Метод удвоения префикса 14.4.2. Поиск образцов 14.4.3. LCP-массивы Глава 15 Дополнительные темы 15.1. Квадратный корень в алгоритмах 15.1.1. Структуры данных 15.1.2. Подалгоритмы 15.1.3. Целые разбиения 15.1.4. Алгоритм Мо 15.2. И снова о деревьях отрезков 15.2.1. Ленивое распространение 15.2.2. Динамические деревья 15.2.3. Структуры данных в вершинах 15.2.4. Двумерные деревья 15.3. Дучи 15.3.1. Разбиение и слияние 15.3.2. Реализация 15.3.3. Дополнительные методы 15.4. Оптимизация динамического программирования 15.4.1. Трюк с выпуклой оболочкой 15.4.2. Оптимизация методом «разделяй и властвуй» 15.4.3. Оптимизация Кнута 15.5. Разное 15.5.1. Встреча в середине 15.5.2. Подсчет подмножеств 15.5.3. Параллельный двоичный поиск 15.5.4. Динамическая связность Приложение Сведения из математики Формулы сумм Множества Математическая логика Функции Логарифмы Системы счисления Библиография Предметный указатель