Олимпиадное программирование с нуля: с чего начать

Уметь программировать заранее не нужно. На многих сайтах с олимпиадными задачами первая задача одна и та же: сложить два числа. Её так и называют, A+B.

Какой язык выбрать

Начать проще с Python: у него короткий синтаксис, и первые задачи решаются в пару строк. Для олимпиад основной язык C++. Программы на нём работают заметно быстрее, часто в десятки раз, а в стандартной библиотеке есть готовые структуры данных и сортировки.

Переходить на C++ удобно, когда вы уверенно пишете циклы, работаете с массивами и строками. Обычно это первые два-три месяца занятий.

Как устроена проверка

Решение олимпиадной задачи это программа, которая читает входные данные и печатает ответ. Вы отправляете код в тестирующую систему, она запускает его на наборе тестов и показывает вердикт:

• OK: все тесты пройдены;
• WA (wrong answer): на каком-то тесте ответ неверный;
• TLE (time limit exceeded): программа не уложилась в ограничение по времени;
• RE (runtime error): программа упала, например из-за выхода за границу массива.

Вердикт WA на седьмом тесте значит, что первые шесть пройдены. Ищите случай, который вы не учли.

В каком порядке учить темы

1. Ввод и вывод, условия, циклы, массивы, строки.
2. Сортировка и простая математика: делимость, остатки, НОД, простые числа.
3. Префиксные суммы, два указателя, двоичный поиск.
4. Перебор, рекурсия, жадные алгоритмы.
5. Динамическое программирование.
6. Графы: обход в ширину и в глубину, кратчайшие пути.
7. Структуры данных: стек, очередь, куча, дерево отрезков.

По нашему опыту, для школьного этапа ВсОШ обычно хватает первых трёх пунктов.

Где решать задачи

• informatics.msk.ru: большой архив, задачи разложены по темам и сложности;
• acmp.ru: много простых задач для первых месяцев;
• Codeforces: регулярные соревнования, для начала подходят раунды Div. 3 и Div. 4;
• платформа «Кружка 102»: 15 уровней, к каждой теме есть теория и задачи с автопроверкой.

Как заниматься, чтобы был результат

• Регулярность важнее объёма. Четыре раза в неделю по часу дают больше, чем один длинный день в выходные.
• Если задача не решается 30-40 минут, посмотрите подсказку или разбор. Потом закройте разбор и напишите решение сами.
• Ведите список нерешённых задач и возвращайтесь к нему раз в неделю.
• Участвуйте в соревнованиях с первого месяца. Решать на время это отдельный навык, его тоже нужно тренировать.

Частые ошибки новичков

• Переполнение. В C++ тип int хранит числа примерно до двух миллиардов, для больших значений нужен long long.
• Лишний текст в выводе. Подсказки вроде «Введите число» тестирующая система считает частью ответа.
• Ограничения не прочитаны. По ним видно, какая сложность алгоритма нужна: при n до 10⁵ квадратичное решение не успеет.
• Медленный ввод в Python. Для больших входных данных читайте через sys.stdin.

Когда идти на олимпиаду

Сразу, как только начались занятия. Школьный этап ВсОШ проходит осенью, и участвовать в нём можно с любым опытом. Следующий шаг описан в статье «Муниципальный этап ВсОШ по информатике».

В «Кружке 102» берут с нуля: начинаем с Python, затем переходим на C++. Занятия в мини-группах по 3-4 ученика или один на один, каждую неделю контест под уровень ученика и разбор. Первое занятие бесплатное, подробности на странице курса информатики.