Введение в олимпиадное программирование
Думаю, каждый, кто увлекается программированием, так или иначе слышал про олимпиады по информатике. Олимпиады по информатике подразумевают под собой решение задач на каком-либо языке программирования.
Что такое олимпиадное программирование?
Олимпиадное программирование состоит из двух частей – проектирования алгоритмов и реализации алгоритмов.
Проектирование алгоритмов. По сути своей, олимпиадное программирование – это придумывание эффективных алгоритмов решения корректно поставленных вычислительных задач. Для проектирования алгоритмов необходимы навыки в решении задач и знание математики. Зачастую решение появляется в результате сочетания хорошо известных методов и новых идей. Важную роль в олимпиадном программировании играет математика. На самом деле четких границ между проектированием алгоритмов и математикой не существует.
Реализация алгоритмов. В олимпиадном программировании решение задачи оценивается путем проверки реализованного алгоритма на ряде тестов. Поэтому придумать алгоритм недостаточно, его еще нужно корректно реализовать, для чего требуется умение программировать. Олимпиадное программирование сильно отличается от традиционной программной инженерии: программы короткие (несколько сотен строк – уже редкость), писать их нужно быстро, а сопровождение после соревнования не требуется.
Для программирования в первую очередь важна практика, хотя оно требует и теоретической подготовки. Это как водить машину: правила движения можно изучить и в классе автошколы, но научиться ездить можно только сидя за рулём автомобиля.
Классификация задач
Задачи по программированию можно разбить на различные "типы". Классификация очень условна. Часто задачу можно отнести к нескольким разделам, а реально она только в одном.
- Рекуррентные соотношения и динамическое программирование.
- Сортировки и последовательности.
- Переборные задачи.
- Структуры данных.
- Задачи на графах.
- Арифметика.
- Геометрия.
- Поиск.
- Разное.
Различные сборники задач и теоретические ресурсы
CSES - Сборник задач на английском языке, задачи расположены в порядке возрастания трудности.
Codeforces - Периодически проводятся онлайн-контесты. Имеются разборы некоторых соревнований. Большой архив задач.
ACMP - Огромный архив задач. На сайте есть методичка и курсы по олимпиадному программированию.
Timus Online Judge - Сайт Уральского государственного университета. Содержит крупнейший в России архив задач с различных соревнований по спортивному программированию, периодически проводятся онлайн-контесты.
Далее, по ходу постов, мы будем разбирать задачи с каждого из этих ресурсов.
Курс на Степике - Олимпиадное программирование. Базовый уровень.
Курс на Степике - Математика для олимпиад по программированию.
Курс на Степике - Спортивное программирование.
Курсы на ACMP
На этом пока все, в следующих постах мы перейдем уже непосредственно к решению различных задач и будем рассматривать различные алгоритмы для решения тех или иных задач. Ресурсы, которые я предоставил вам помогут вам окунуться в мир олимпиадного программирования самостоятельно, потому что как я и говорил ранее - Для программирования в первую очередь важна практика.