Что дальше

Сорок пять занятий назад курс начинался с ввода и вывода. Стоит проговорить вслух, что осталось в руках — обычно этот список недооценивают.

• Читать условие с ограничениями и понимать, какое решение в нём ждут
• Прикидывать число операций до того, как написан код
• Двоичный поиск и поиск по ответу
• Два указателя и скользящее окно
• Жадность — и, что важнее, недоверие к ней без контрпримера
• Перебор с отсечениями, перебор подмножеств и перестановок, встреча посередине
• Делимость, НОД, простые числа, решето, системы счисления
• Комбинаторику со степенями и сочетаниями по модулю
• Графы: как их увидеть в условии, обход в ширину и в глубину
• Динамику: одномерную и по таблице, с восстановлением ответа и с экономией памяти

Этого набора достаточно, чтобы уверенно чувствовать себя на школьном и муниципальном этапах и брать часть задач регионального. Дальше начинается то, чего в курсе не было.

Контест был устроен так, что каждая задача опирается на свою тему. Посмотрите, какие не пошли, и вернитесь точечно — перечитывать весь курс незачем.

И отдельно тот случай, который таблицей не лечится: тему знал, но не узнал. Если задача разобралась за минуту после прочтения признака — перечитывать занятие бесполезно, нужна насмотренность. Решайте задачи там, где тема не написана в заголовке; об этом ниже.

Курс закрыл базу. Дальше темы делятся на несколько направлений — привожу их с тем, какие задачи без них не берутся, потому что «выучить структуру данных» само по себе бессмысленно.

Структуры данных

• Куча — когда на каждом шаге нужен минимум из меняющегося набора. Планировщики, слияние списков, алгоритм Дейкстры.
• Система непересекающихся множеств — когда объекты постепенно объединяются в группы и надо быстро отвечать, в одной ли группе двое. Динамическая связность, остовные деревья.
• Дерево отрезков — когда запросы «сумма или минимум на отрезке» перемежаются с изменениями элементов. Ровно та задача из проверки выше, где честное суммирование даёт двадцать миллиардов операций.

Графы

• Дейкстра — кратчайший путь, когда у рёбер есть вес. Обход в ширину здесь уже не годится.
• Топологическая сортировка — порядок дел с зависимостями; заодно динамика на графе без циклов.
• Остовное дерево — связать всё дешевле всего.

Динамика

• По подмножествам — когда состояние это «какие из $n \le 20$ объектов уже использованы». Задача коммивояжёра, расстановки.
• По цифрам — когда считать надо среди чисел до $10^{18}$, а перебор исключён. Та самая тема, в которую не надо было лезть в задаче 11 — но которая нужна, когда диапазон и правда огромен.

Строки

• Хеши и префикс-функция — сравнение подстрок и поиск вхождений за линию.

Математика

• Быстрое возведение в степень и обратный элемент по модулю — без них не считаются сочетания по простому модулю в больших ограничениях.
• Геометрия — векторное произведение, принадлежность, выпуклая оболочка.

Порядок разумно взять такой: сначала Дейкстра и система непересекающихся множеств, потом дерево отрезков, потом динамика по подмножествам. Строки и геометрию — позже, они реже встречаются на ранних этапах.

Регулярность важнее объёма

Час в день лучше семи часов в воскресенье. Навык узнавания набирается количеством разных условий, а не длительностью подходов.

Сколько сидеть над задачей

Тридцать-сорок минут без всякого продвижения — сигнал открыть разбор. Дольше сидеть вредно: вы не придумываете, а перебираете одно и то же по кругу.

Но открыть разбор — это не «прочитать и пойти дальше». Прочитали идею — закрыли и написали код сами. Задача, разбор которой вы поняли, но не написали, не решена.

Дорешивание

Главная привычка соревнующегося. После любого контеста возьмите задачи, которые не взяли, и доведите их до принятого решения — без ограничения времени, с разбором, сколько понадобится. Рост даёт именно это, а не сами контесты.

Виртуальные контесты

Прошедший контест можно решать в режиме соревнования: таймер, никаких разборов. Это единственный способ тренировать то, что на настоящем соревновании ломается первым, — распределение времени и решение, какую задачу брать следующей.

Где решать

• Codeforces — главная площадка. Соревнования уровня Div. 3 и Div. 4 рассчитаны на начинающих и хорошо ложатся на этот курс.
• acmp.ru — задачи по темам, с уровнями сложности, на русском.
• informatics.msk.ru — курсы дистанционной подготовки, много задач школьных этапов.

Про олимпиады

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

Этот курс открытый и асинхронный: никаких сроков, никакого преподавателя, всё проверяет автомат. Дальше на EduBrick есть курсы с занятиями и разбором работ.

• Олимпиадное программирование: базовый курс — с нуля до муниципального этапа, Python. Если этот курс дался тяжело и хочется пройти то же самое, но с преподавателем.
• Олимпиадное программирование: продвинутый курс — от муниципа к региону. C++, структуры данных, графы, динамика. Прямое продолжение того, на чём вы остановились.
• Олимпиадное программирование: курс профи — регион и перечневые олимпиады: продвинутые структуры, графы, динамика, математика.

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

Напоследок

Самое ценное, что стоит унести из курса, — не список приёмов, а привычка задавать условию три вопроса: что говорят ограничения, что здесь состояние и можно ли проверить готовый ответ быстрее, чем его найти. Приёмы забудутся и перечитаются за вечер. Привычка — нет.

Спасибо, что дошли до конца.