Спортивное программирование

Вступление
Предисловие
От издательства
Об авторах этой книги
Список сокращений
Глава 1. Введение
1.1. Олимпиадное программирование
1.2. Как стать конкурентоспособным
1.2.1. Совет 1: печатайте быстрее!
1.2.2. Совет 2: быстро классифицируйте задачи
1.2.3. Совет 3: проводите анализ алгоритмов
1.2.4. Совет 4: совершенствуйте свои знания языков программирования
1.2.5. Совет 5: овладейте искусством тестирования кода
1.2.6. Совет 6: практикуйтесь и еще раз практикуйтесь!
1.2.7. Совет 7: организуйте командную работу (для ICPC)
1.3. Начинаем работу: простые задачи
1.3.1. Общий анализ олимпиадной задачи по программированию
1.3.2. Типичные процедуры ввода/вывода
1.3.3. Начинаем решать задачи
1.4. Задачи Ad Hoc
1.5. Решения упражнений, не помеченных звездочкой
1.6. Примечания к главе 1
Глава 2. Структуры данных и библиотеки
2.1. Общий обзор и мотивация
2.2. Линейные структуры данных – встроенные библиотеки
2.3. Нелинейные структуры данных – встроенные библиотеки
2.4. Структуры данных с реализациями библиотек, написанными авторами этой книги
2.4.1. Граф
2.4.2. Система непересекающихся множеств
2.4.3. Дерево сегментов
2.4.4. Дерево Фенвика
2.5. Решения упражнений, не помеченных звездочкой
2.6. Примечания к главе 2
Глава 3. Некоторые способы решения задач
3.1. Общий обзор и мотивация
3.2. Полный перебор
3.2.1. Итеративный полный перебор
3.2.2. Рекурсивный полный перебор (возвратная рекурсия)
3.2.3. Советы
3.3. «Разделяй и властвуй»
3.3.1. Интересное использование двоичного поиска
3.4. «Жадные» алгоритмы
3.4.1. Примеры
3.5. Динамическое программирование
3.5.1. Примеры DP
3.5.2. Классические примеры
3.5.3. Неклассические примеры
3.6. Решения упражнений, не помеченных звездочкой
3.7. Примечания к главе 3
Глава 4. Графы
4.1. Общий обзор и мотивация
4.2. Обход графа
4.2.1. Поиск в глубину (Depth First Search, DFS)
4.2.2. Поиск в ширину (Breadth First Search, BFS)
4.2.3. Поиск компонент связности (неориентированный граф)
4.2.4. Закрашивание – Маркировка/раскрашивание компонент связности
4.2.5. Топологическая сортировка (направленный ациклический граф)
4.2.6. Проверка двудольности графа
4.2.7. Проверка свойств ребер графа через остовное дерево DFS
4.2.8. Нахождение точек сочленения и мостов (неориентированный граф)
4.2.9. Нахождение компонент сильной связности (ориентированный граф)
4.3. Минимальное остовное дерево
4.3.1. Обзор
4.3.2. Алгоритм Краскала
4.3.3. Алгоритм Прима
4.3.4. Другие варианты применения
4.4. Нахождение кратчайших путей из заданной вершины во все остальные (Single – Source Shortest Paths, SSSP)
4.4.1. Обзор
4.4.2. SSSP на невзвешенном графе
4.4.3. SSSP на взвешенном графе
4.4.4. SSSP на графе, имеющем цикл с отрицательным весом
4.5. Кратчайшие пути между всеми вершинами
4.5.1. Обзор
4.5.2. Объяснение алгоритма DP Флойда–Уоршелла
4.5.3. Другие применения
4.6. Поток
4.6.1. Обзор
4.6.2. Метод Форда–Фалкерсона
4.6.3. Алгоритм Эдмондса–Карпа
4.6.4. Моделирование графа потока – часть I
4.6.5. Другие разновидности задач, использующих поток
4.6.6. Моделирование графа потока – часть II
4.7. Специальные графы
4.7.1. Направленный ациклический граф
4.7.2. Дерево
4.7.3. Эйлеров граф
4.7.4. Двудольный граф
4.8. Решения упражнений, не помеченных звездочкой
4.9. Примечания к главе 4
Глава 5. Математика
5.1. Общий обзор и мотивация
5.2. Задачи Ad Hoc и математика
5.3. Класс Java BigInteger
5.3.1. Основные функции
5.3.2. Дополнительные функции
5.4. Комбинаторика
5.4.1. Числа Фибоначчи
5.4.2. Биномиальные коэффициенты
5.4.3. Числа Каталана
5.5. Теория чисел
5.5.1. Простые числа
5.5.2. Наибольший общий делитель и наименьшее общее кратное
5.5.3. Факториал
5.5.4. Нахождение простых множителей с помощью оптимизированных операций пробных разложений на множители
5.5.5. Работа с простыми множителями
5.5.6. Функции, использующие простые множители
5.5.7. Модифицированное «решето»
5.5.8. Арифметические операции по модулю
5.5.9. Расширенный алгоритм Евклида: решение линейного диофантова уравнения
5.6. Теория вероятностей
5.7. Поиск цикла
5.7.1. Решение(я), использующее(ие) эффективные структуры данных
5.7.2. Алгоритм поиска цикла, реализованный Флойдом
5.8. Теория игр
5.8.1. Дерево решений
5.8.2. Знание математики и ускорение решения
5.8.3. Игра Ним
5.9. Решения упражнений, не помеченных звездочкой
5.10. Примечания к главе 5
Глава 6. Обработка строк
6.1. Обзор и мотивация
6.2. Основные приемы и принципы обработки строк
6.3. Специализированные задачи обработки строк
6.4. Поиск совпадений в строках
6.4.1. Решения с использованием библиотечных функций
6.4.2. Алгоритм Кнута–Морриса–Пратта
6.4.3. Поиск совпадений в строках на двумерной сетке
6.5. Обработка строк с применением динамического программирования
6.5.1. Регулирование строк (редакционное расстояние)
6.5.2. Поиск наибольшей общей подпоследовательности
6.5.3. Неклассические задачи обработки строк с применением динамического программирования
6.6. Суффиксный бор, суффиксное дерево, суффиксный массив
6.6.1. Суффиксный бор и его приложения
6.6.2. Суффиксное дерево
6.6.3. Практические приложения суффиксного дерева
6.6.4. Суффиксный массив
6.6.5. Практические приложения суффиксного массива
6.7. Решения упражнений, не помеченных звездочкой
6.8. Примечания к главе
Глава 7. (Вычислительная) Геометрия
7.1. Обзор и мотивация
7.2. Основные геометрические объекты и библиотечные функции для них
7.2.1. Нульмерные объекты: точки
7.2.2. Одномерные объекты: прямые
7.2.3. Двумерные объекты: окружности
7.2.4. Двумерные объекты: треугольники
7.2.5. Двумерные объекты: четырехугольники
7.2.6. Замечания о трехмерных объектах
7.3. Алгоритмы для многоугольников с использованием библиотечных функций
7.3.1. Представление многоугольника
7.3.2. Периметр многоугольника
7.3.3. Площадь многоугольника
7.3.4. Проверка многоугольника на выпуклость
7.3.5. Проверка расположения точки внутри многоугольника
7.3.6. Разделение многоугольника с помощью прямой линии
7.3.7. Построение выпуклой оболочки множества точек
7.4. Решения упражнений, не помеченных звездочкой
7.5. Замечания к главе
Глава 8. Более сложные темы
8.1. Обзор и мотивация
8.2. Более эффективные методы поиска
8.2.1. Метод поиска с возвратами с применением битовой маски
8.2.2. Поиск с возвратами с интенсивным отсечением
8.2.3. Поиск в пространстве состояний с применением поиска в ширину или алгоритма Дейкстры
8.2.4. Встреча в середине (двунаправленный поиск)
8.2.5. Поиск, основанный на имеющейся информации: A* и IDA*
8.3. Более эффективные методы динамического программирования
8.3.1. Динамическое программирование с использованием битовой маски
8.3.2. Некоторые общие параметры (динамического программирования)
8.3.3. Обработка отрицательных значений параметров с использованием метода смещения
8.3.4. Превышение лимита памяти? Рассмотрим использование сбалансированного бинарного дерева поиска как таблицы запоминания состояний
8.3.5. Превышение лимита памяти/времени? Используйте более эффективное представление состояния
8.3.6. Превышение лимита памяти/времени? Отбросим один параметр, будем восстанавливать его по другим параметрам
8.4. Декомпозиция задачи
8.4.1. Два компонента: бинарный поиск ответа и прочие
8.4.2. Два компонента: использование статической задачи RSQ/RMQ
8.4.3. Два компонента: предварительная обработка графа и динамическое программирование
8.4.4. Два компонента: использование графов
8.4.5. Два компонента: использование математики
8.4.6. Два компонента: полный поиск и геометрия
8.4.7. Два компонента: использование эффективной структуры данных
8.4.8. Три компонента
8.5. Решения упражнений, не помеченных звездочкой
8.6. Замечания к главе
Малораспространенные темы
Глава 9. Общий обзор и мотивация
9.1. Задача 2-SAT
9.2. Задача о картинной галерее
9.3. Битоническая задача коммивояжера
9.4. Разбиение скобок на пары
9.5. Задача китайского почтальона
9.6. Задача о паре ближайших точек
9.7. Алгоритм Диница
9.8. Формулы или теоремы
9.9. Алгоритм последовательного исключения переменных, или метод Гаусса
9.10. Паросочетание в графах
9.11. Кратчайшее расстояние на сфере (ортодромия)
9.12. Алгоритм Хопкрофта–Карпа
9.13. Вершинно и реберно не пересекаюшиеся пути
9.14. Количество инверсий
9.15. Задача Иосифа Флавия
9.16. Ход коня
9.17. Алгоритм Косараджу
9.18. Наименьший общий предок
9.19. Создание магических квадратов (нечетной размерности)
9.20. Задача о порядке умножения матриц
9.21. Возведение матрицы в степень
9.22. Задача о независимом множестве максимального веса
9.23. Максимальный поток минимальной стоимости
9.24. Минимальное покрытие путями в ориентированном ациклическом графе
9.25. Блинная сортировка
9.26. Ро-алгоритм Полларда для разложения на множители целых чисел
9.27. Постфиксный калькулятор и преобразование выражений
9.28. Римские цифры
9.29. k-я порядковая статистика
9.30. Алгоритм ускоренного поиска кратчайшего пути
9.31. Метод скользящего окна
9.32. Алгоритм сортировки с линейным временем работы
9.33. Структура данных «разреженная таблица»
9.34. Задача о ханойских башнях
9.35. Замечания к главе
Приложение A. uHunt
Приложение B. Благодарности
Список используемой литературы
Предметный указатель