Подготовка к олимпиадам по программированию

Как подготовиться к олимпиадам по программированию

Плотников В.Е.

Среди всех школьных предметов информатика выделяется как наиболее динамичный предмет. В условиях постоянного развития и совершенствования как технических, так и программных средств, меняются технологии проведения олимпиад по информатике, повышается уровень сложности олимпиадных задач. Задания олимпиады, представляя информатику как точную науку, а не как набор знаний и навыков работы в конкретных программных средах, фокусируют внимание учеников на базовых понятиях и математических основах информатики, то есть на том, что им будет необходимо при дальнейшем обучении в вузах. Фактически, они являются олимпиадами по программированию. Для успешного участия в олимпиадах учащийся должен знать и применять при решении задач определенный набор алгоритмов, отлично владеть техникой программирования на определенных языках, а также специальными приемами программирования.

Как подготовить школьников для успешного участия в олимпиадах по информатике в рамках школьной программы, если изучение программирования начинается только в 8, 9 классах? Как лучше организовать подготовку школьников во внеурочное время? Что требуется от учителя для качественной подготовки школьников к олимпиаде? - Подобные вопросы ставит перед собой каждый учитель информатики. С чего начинать?!

В первую очередь надо выбрать язык программирования. Из популярных сейчас вариантов есть C++, Python, Java, Pascal. Надо понимать при выборе, что Pascal на олимпиадах школьников по программированию не пригодится, потому что его отменили. Python часто используется на олимпиадах, очень многих школьников учат ему, но в реальности он является интерпретатором и на нем нельзя решить все задачи, потому что он медленный и поможет решить лишь несколько простых задач, например, задачи с длинной арифметикой. Либо что-то быстро написать – какой-то скрипт для тестирования. Но в целом рекомендуемый язык для олимпиад по информатике – это C++.

В C++ надо знать базовый синтаксис, стандартные структуры данных в библиотеке STL, классы функций в С/C++, уметь работать со списками, векторами, Map, множествами и подобными базовыми классами. Освоить язык проще, если изучить сначала самые базовые вещи и решать самые простые задачи: ввод, преобразование данных, операторы цикла, перебор. Для начинающих лучше всего брать задачи с онлайн-архивных ресурсов – например, acm.timus.ru или с informatics.mccme.ru. Начинать лучше с тех задач, которые на платформе решили больше всего пользователей. Потом надо переходить к базовым алгоритмам, например, начать с алгоритма сортировки, двоичного поиска, простейших понятий о динамическом программировании. При подготовке важно уделять внимание самым разным темам и быть готовым ко всему. Например, если на олимпиаде дают восемь задач, то скорее всего все восемь задач будут на разные темы. Но главное – это понимать, что в информатике без серьезной математической подготовки вероятность успеха невелика. Поэтому приоритетом для меня является математическая подготовка учащихся.

По математике нужно знать следующее: делимость, свойства делимости, представление целых чисел, геометрические задачи. Геометрия в информатике немного другая, не такая, как в школе. 90% задач по геометрии в информатике решаются через векторы. В векторном представлении формулы выглядят совсем не страшными. Можно решать задачи на e-maxx.ru, acm.mipt.ru или codeforces.com и потом участвовать в онлайн-соревнованиях.

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

С формулами типа Герона с корнями, которые даются в школе, никакие задачи по информатике не решишь. А вот тригонометрию знать очень желательно, хотя бы для того, чтобы понять векторы. Тригонометрия используется в любых геометрических задачах. Например, нужно посчитать расстояние между двумя отрезками, проверить, пересекаются ли отрезки, посчитать расстояние от точки до прямой, взаимное расположение окружностей и т.д. Проще всего это решить, проверяя знак скалярного произведения векторов. По знаку косинуса определяется, тупой угол или острый. Длина перпендикуляра находится через площадь треугольника. То есть надо знать формулу площади треугольника через основание и высоту. Это самые базовые задачи, обычно бывают комбинации идей, при подготовке одаренных ребят к олимпиаде по программированию.

Также для участия в олимпиадах надо знать динамическое программирование. Задачи на динамику будут практически в каждой олимпиаде, включая региональные. Это очень важная тема. Уметь оценивать скорость работы программы, асимптотику, растет ли скорость как сложность программы от N, растет ли как N² или как логарифм.

Классический пример задачи: черепашка движется из верхнего левого угла в правый нижний, в клетках поля написаны отрицательные числа. Она может двигаться только вниз или вправо. Нужно пройти и собрать наибольшую сумму. Это задача на двумерную динамику. Заполняется таблица по очереди, берется значение N. В каждой клетке ответ равен максимуму двух соседей. Бывают задачи на последовательность нулей и единиц, в которых нет двух единиц подряд. Это нужно решать через формулу Фибоначчи.

Что еще по математике стараюсь дать своим ученикам? Хотя в стандартной сишной (C) библиотеке сортировка есть, но все равно уметь написать алгоритмы сортировки лучше, чем за N². Например, знать сортировку слияния (Merge sort).

Нужно уметь решать уравнения методом двоичного поиска. Задача может звучать так: «найти корень уравнения, если известно, что в одной точке величина отрицательная, в другой – положительная». Для решения всякий раз берем середину отрезка и смотрим, поменялся ли знак в этой середине.

На олимпиаде надо знать вещи типа алгоритма Эвклида для простых чисел. Надо уметь находить взаимную простоту чисел, уметь работать с остатками от деления по модулю. Если сложение, умножение, вычитание – это довольно простые вещи, то для деления будет нужен нетривиальный алгоритм быстрого возведения в степень. В очень многих олимпиадах ответ требуется вывести в виде остатка от деления на какое-то большое простое число.

Из того, что не проходят в школе, надо также знать темы, касающиеся теории графов: что такое граф, представление графа в виде списка, в виде матрицы и в виде списка вершин, базовые алгоритмы поиска BFS/DFS, обход в ширину, обход в глубину, основные деревья, компоненты связности, на которые распадается граф. Надо научиться решать переборные задачи, рекурсии типа задачи обхода доски ходом коня.

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

Но даже ребята сделали разбор задачи, желательно ее прорешать и сдать, чтобы выяснить, что они этот алгоритм освоили. В качестве примера разбора возьмем классическую олимпиадную задачу.

Задача B. Рыцари и лжецы

Имя входного файла: standard input

Имя выходного файла: standard output

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мебибайта

На острове Буяне жили N человек, каждый из которых был либо рыцарем, либо лжецом. Все они встали в круг. Рыцари говорят только правду, лжецы всегда только лгут. Каждому человеку в кругу задали вопрос: «Кто ты и кто твой сосед слева: рыцарь или лжец?». При этом каждый человек сказал, что он — рыцарь. А ответы всех людей о левом соседе были записаны в следующем формате: ответ «он рыцарь» обозначался за 1, ответ «он лжец» — за 0.

Все ответы были записаны в строку через пробел в порядке опроса (совпадающем с порядком обхода). Последний спрошенный человек отвечал на вопрос о первом.

Написать программу, которая по ответам жителей определяет, какое количество рыцарей заведомо присутствует в круге.

Решение: Задача B. Рыцари и лжецы

Имя входного файла: standard input

Имя выходного файла: standard output

Ограничение по времени: 1 секунда

Ограничение по памяти: 64 мебибайта

Задача о рыцарях и лжецах — переборная. К счастью, перебор можно ограничить всего лишь двумя вариантами: первый человек — рыцарь или лжец? Предположив один из двух вариантов, можно однозначно вычислить, рыцарь или лжец следующий (так как человек с известным статусом сказал про человека слева) и так далее по индукции до первого. В процессе индукции можно считать, сколько у нас рыцарей. Когда по индукции выяснен статус первого жителя, проверяем, соответствует ли он нашему предположению. Если же соответствующих вариантов 2, то выбираем тот, в котором меньше рыцарей (то есть заведомо присутствует столько-то, а может быть, есть и больше).

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