Путь к олимпиадному программированию
Последовательность подготовки по книге Антти Лааксонена: двигайтесь по главам, разбирайте примеры и проверяйте каждый новый приём на задачах.
- изучай
- программируй
- решай контесты
Как работать с темой: прочитайте главу, воспроизведите алгоритмы самостоятельно, решите задачи и разберите случаи, на которых решение ошибается. Ссылки на готовые материалы сайта добавлены к соответствующим главам.
Начните с основы
Разберитесь с форматом соревнований, научитесь писать и оценивать решения.
Введение
Техника программирования
Эффективность
- Временная сложность
- Сравнение алгоритмов
- Примеры оценки решений
Освойте основные приёмы
Сортировка, структуры данных и первые задачи на динамику.
Сортировка и поиск
- Алгоритмы сортировки
- Задачи с сортировкой
- Двоичный поиск
Структуры данных
- Векторы
- Множества и отображения
- Очереди с приоритетом
Динамическое программирование
- Оптимальные решения
- Подсчёт решений
- Подпоследовательности, сетки, рюкзак
Перейдите к графам
Изучите обходы, маршруты и методы ускорения алгоритмов.
Алгоритмы на графах
- Представление графа
- DFS и BFS
- Кратчайшие пути, DAG, остовные деревья
Избранные вопросы проектирования алгоритмов
- Параллельный просмотр разрядов
- Два указателя и скользящее окно
- Троичный поиск
Углубите работу со структурами
Запросы к массивам и деревьям, затем математические инструменты.
Запросы по диапазону
- Запросы суммы и минимума
- Двоичное индексное дерево
- Дерево отрезков
Алгоритмы на деревьях
- Обход и диаметр дерева
- Предки, поддеревья, пути
- Декомпозиция дерева
Математика
- Теория чисел и комбинаторика
- Матрицы и вероятность
- Теория игр
Изучите специальные темы
Материал для задач, в которых базовых приёмов уже недостаточно.
Дополнительные алгоритмы на графах
- Сильная связность
- Эйлеровы и гамильтоновы пути
- Максимальный поток
Геометрия
- Точки, прямые и площади
- Заметающая прямая
- Ближайшая пара и выпуклая оболочка
Алгоритмы работы со строками
- Префиксное дерево
- Хеширование и Z-алгоритм
- Суффиксные массивы
Дополнительные темы
- Алгоритм Мо
- Ленивое распространение
- Оптимизация динамического программирования
Основа маршрута: Антти Лааксонен, «Олимпиадное программирование. Изучение и улучшение алгоритмов на соревнованиях» (ДМК Пресс, 2018).