Глеб Евстропов, ведущий разработчик «Яндекса» и руководитель службы поисковых подсказок, член жюри Всероссийской олимпиады школьников по информатике, рассказал, как начать заниматься спортивным программированием, за какие задачи браться в первую очередь и какие преимущества даёт участие в олимпиадах.
Чек-лист: олимпиадное программирование — с чего начать школьнику?
Мария Передок
Олимпиадное или спортивное программирование — это участие в соревнованиях по решению нетривиальных алгоритмических задач. Оно позволяет получить фундаментальные знания, научиться эффективнее писать код и подготовиться к дальнейшей карьере — победителей и призеров олимпиад охотно нанимают ведущие IT-компании.
На старте
Программирование — это умение превращать объекты из реальных задач в абстрактные сущности и выражать их взаимодействие на языке программного кода. Поэтому главное условие для изучения программирования — абстрактное мышление, на которое сильно влияет уровень преподавания школьной математики.
Если вам интересно программирование, и у вас уже начало формироваться абстрактное мышление, с поддержкой увлечённого педагога довольно быстро освоите базовые знания, достаточные для участия в олимпиадах. Однако подготовиться к соревнованиям можно и самостоятельно, главное — сопровождать каждую пройденную тему, даже самую простую, усиленной практикой.
С чего начать?
Сперва нужно освоить какой-нибудь язык программирования. Например, раньше учебным языком был Pascal. Сейчас принято начинать с Python, который популярен среди тех, кто хочет быстро научиться писать код. Этот язык очень дружелюбный к начинающим, у него есть подробная и понятная документация и большое количество библиотек. Но чтобы продолжать участвовать в более сложных олимпиадах, надо будет рано или поздно овладеть C++.
Минимум тем, которые нужно изучить: переменные, операторы присваивания, логические и арифметические операции, условные операторы, потом — массивы и циклы, процедуры и функции. Для того, чтобы в них разобраться, можно, например, посмотреть курс Михаила Густокашина по C++ на Stepik. С этой базой можно решать первые олимпиадные задачи.
Как тренироваться?
Для программирования в первую очередь важна практика, хотя оно требует и теоретической подготовки. Это как водить машину: правила движения можно изучить и в классе автошколы, но научиться ездить можно только сидя за рулём автомобиля.
Я думаю, есть два основных способа выучить программирование:
«Задачное» обучение — изучение конструкции языка через решение абстрактных задач. Например, когда надо прочитать все числа из файла и подсчитать сумму нечетных.
Проектное обучение, при котором учащийся получает наглядный результат своей работы, небольшой работающий «продукт».
Олимпиадное программирование хорошо тем, что практиковаться можно и самостоятельно, без помощи преподавателя. Есть платформы, на которых доступно большое количество олимпиадных задач. Решаешь задачу, пишешь код, отправляешь его на проверку и тут же получаешь результат. Мгновенная обратная связь мотивирует продолжать заниматься программированием.
Например, есть сайт «Информатикс», созданный коллективом московских преподавателей олимпиадной информатики. На нём есть и теоретические материалы: например, вводные лекции по Python, к которым прикреплены примеры олимпиадных задач. Прошёл тему — и сразу выполняешь по ней задание.
Самая популярная платформа для решения задач — это codeforces.com, которую создал и активно развивает Михаил Мирзаянов. На ней постоянно проводятся контесты (соревнования), открытые для всех желающих. Они рассчитаны на людей с разным уровнем: от тех, кто только вчера узнал базовые конструкции языка, до настоящих профессионалов, которые выигрывали международные соревнования и занимаются спортивным программированием уже много лет.
Путь к успеху — решать, решать, а потом ещё немного решать. Регулярно писать контесты — хотя бы один раз в неделю, а лучше два. Если решение задачи после долгих раздумий так и не нашлось, читайте её разбор.
Когда сталкиваетесь с незнакомым алгоритмом — знакомьтесь с ним, смотрите лекции на эту тему, изучайте статьи, форумы и книги. Например, «Алгоритмы: построение и анализ» Томаса Кормена и соавторов. Так выглядят дни тех, кто занимается олимпиадным программированием уже профессионально.
А ещё решать задачи гораздо приятнее и полезнее в команде. Ребята, которые занимаются в сообществе, как правило, достигают больших успехов.
Продолжение обучения
Когда человек освоил базу и знает конструкции языка, ему пора идти дальше: углубленно изучать теорию и разнообразные алгоритмы, которые позволяют по-новому работать с уже известными комбинаторными объектами. Знать алгоритмы и уметь применять сложные трюки — это хорошо, но задача никогда не состоит только из применения готовых знаний. Надо уметь сопоставлять разные параметры, вспоминать алгоритмы и модифицировать их для дальнейшего применения.
В любой задаче есть своя уникальная идея — даже если ты видел до этого тысячу других идей и задач, то 1001-я всё равно будет новой.
До многих вещей можно дойти самостоятельно, но проще и быстрее будет, если знающие люди расскажут готовые способы решения. Самый действенный путь — общаться с единомышленниками и посещать места, где делятся знаниями и опытом: выездные школы и сборы. Например, есть смена «Алгоритмы и анализ данных» в «Сириусе», где много времени уделяется тому, чтобы помочь ребятам прокачать необходимые навыки для участия в олимпиадах по информатике. Поищите и регулярные занятия, которые можно посещать круглый год: например, кружки олимпиадного программирования, которые работают в вашем городе.
Самостоятельное обучение по книгам и материалам из интернета — это длинный и сложный путь, хотя поиск самой информации и не составит труда. В частности, на сайте MAXimal собраны 145 алгоритмов для решения разных задач, а также в открытом доступе опубликованы книги по алгоритмам, оптимизации, С++ и Java.
Тактическое преимущество
Чтобы эффективно выполнять задачи, надо понимать, решение каких из них принесет наибольшую пользу в будущем.
Я подразделяю задачи на четыре уровня сложности:
-
Первый уровень: даже не замечаешь, как решил задачу. Решение приходит в голову сразу же, как только прочитал условие. Это бесполезные с точки зрения опыта задачи, хотя их и можно встретить на олимпиаде. Если есть возможность их не решать — не решайте.
Второй уровень: задание вызывает небольшое напряжение. Сходу его не решить, хотя и примерно ясно, в каком направлении нужно двигаться. На такие задания уходит минут 5-15. Подумал, попробовал наиболее очевидный вариант решения или два — и решил.
Третий уровень: трудные, но подъёмные задачи. Для выполнения придётся опробовать или с нуля придумать новую идею. Не просто собрать решение из готовых кирпичиков, а распутать головоломку. Пока выполняешь такие задачи, осознаёшь то, с чем раньше не сталкивался, возможно, пробуешь малознакомые алгоритмы. На обдумывание может уйти час, а на написание кода — ещё пару часов. Это тяжело и требует волевых усилий, но очень полезно.
Четвёртый уровень: не для тебя (пока). Например, ты семиклассник, а для решения задачи нужны знания университетских математических формул и громоздких алгоритмов. Прочитал разбор и всё равно вообще ничего не понял. Ты можешь попытаться разобраться и в итоге выполнить это задание, потратив колоссальное время, но получится неэффективно для общего результата.
На смене в «Сириусе» ребята, например, решали такие задачи:
Задача 1. Еловая аллея
Задача 2. Петя и снегоуборочная машина
Ошибки при подготовке к олимпиаде
Ударяться в крайности. «Я всегда дохожу до решения сам и никогда никуда не подсматриваю. Если мне нужно будет потратить три недели, чтобы решить задачу, то я потрачу три недели». До всего доходить самостоятельно — это круто, но неэффективно. К тому же, этот путь потребует слишком много силы воли, которая редко у кого встречается, а также может привести к выгоранию и утрате мотивации.
Тут же сдаваться. «Если я не понял, как решать задачу за 15 минут, то я узнаю, как она решается, прочитав её разбор». При помощи ресурса Codeforces, про который я говорил выше, можно узнать, как автор видел решение этой задачи, и как эту задачу решили бы другие люди. Но ты не дал себе шанса подумать как следует, упустил возможность найти решение самостоятельно, а это плохо для опыта и развития интуиции.
Решать только те задачи, которые нравятся. В олимпиадном программировании существуют разные типы задач: некоторые требуют в первую очередь развитого математического аппарата (например, знания теории чисел), в других идёт упор на написание кода, в-третьих — на математику (системы уравнений, теория чисел), а иногда — комбинаторику (графы). Углубляться всегда надо в те области, где возникло сопротивление. Для успеха на соревнованиях полезнее решить пять задач на нелюбимую тему, чем на ту, которая легко даётся.
Не уделять достаточно внимания коду. В процессе написания программы наброски решения переводятся на формальный язык. Иногда ты за пять минут находишь решение и потом пару часов пишешь код, а бывает и наоборот. Писать код так, чтобы в нём было меньше ошибок, способность эти ошибки находить и исправлять — навык, который можно и нужно нарабатывать. Чем больше пишешь код, тем лучше начинаешь это делать. Также полезно обсуждать с другими людьми, как писать программы с меньшим количеством ошибок и читать чужой код.
Что дают олимпиады?
Льготы при поступлении. Есть линейка всероссийских предметных олимпиад, диплом которых — билет в вуз на бюджетное место.
Олимпиадный опыт помогает проходить собеседования в крупные компании, так как на них очень часто дают олимпиадные задачи.
Призовое место — это весомое дополнение к любому портфолио и резюме. Перспектива повышать уровень олимпиадного программирования и дальше, поехать на международные соревнования. Например, на международный чемпионат по алгоритмическому программированию ICPC, который считается самым престижным соревнованием в мире.
Возможность попасть в специальные летние или зимние школы, на сборы, в проекты вроде «Сириуса», и стать частью сплоченного сообщества.
Даже если вы не будете занимать призовые места на олимпиадах, участие в них позволит набраться фундаментальных знаний и опыта разработки, разовьёт умение размышлять.
Источник: