Предупреждение. Данная статья отражает исключительно мнение автора. Автор не претендует на верность всех утверждений. Статья предоставляется “как есть”, и автор не несет ответственности за какие бы то ни было отрицательные последствия ее прочтения и использования :)

Многие студенты, начав участвовать в олимпиадах, задаются вопросом: “Как добиться каких-либо значительных результатов?“. Здесь есть два варианта:

  1. вы – гений, в этом случае, скорее всего, вам не надо читать дальше :)
  2. вы – обычный студент, тогда единственный ответ – тренироваться, об этом и пойдет речь.

В последнее время меня несколько раз спрашивали “как надо готовиться к ACM ICPC“? В свое время и я задавал его некоторым личностям, но так и не получил вразумительного ответа. Поиск в Интернет также практически ничего не дал – видимо, известные корифеи спортивного программирования не очень любят писать. В общем пришлось, как всегда, доходить практически до всего самому, и здесь мне пригодился 7-летний опыт занятий некоторым, довольно специфическим видом спорта. Так или иначе, не без помощи руководителя и товарищей, я получил некоторый опыт, которым и постараюсь поделиться с вами – может кому-нибудь и пригодится.

Прежде всего необходимо уяснить, что олимпиады по программированию, особенно ACM ICPC, – это спорт. И подготовка к ним должна быть как к спортивным состязанием. Это включает постоянные упорные тренировки, удачи и неудачи, взлеты и падения.

Тренироваться нужно как можно чаще. Не реже 1-2 раз в неделю (а непосредственно перед соревнованиями желательно каждый день) делать командную тренировку, а в течение недели готовиться поодиночке.

Есть 3 направления подготовки, которые должны идти параллельно и взаимно дополнять друг друга:

  1. теоретическая (математика, алгоритмы и структуры данных);
  2. практическая (стандарты, языки и ООП, решение задач);
  3. командная.

Теоретическая подготовка: математика

Часто можно услышать в качестве причины нежелания участвовать в олимпиадах такое утверждение: “Да там же сплошная математика!” Это одновременно и правда, и не совсем. В самом деле, чтобы успешно выступать на соревнованиях необходимо знать почти весь школьный курс математики, некоторые сведения из теории графов, теории чисел и т.п. Но в реальности все не так страшно. Школьный курс математики должны знать все, кто учился в школе, а из нешкольных разделов в большинстве случаев достаточно понимания определений и некоторого знакомства с базовыми теоремами и приемами. Этого будет хватать для большинства обычных соревнований, но может быть недостаточным для контестов от МГУ на Петрозаводских сборах :)

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

Несколько направлений помимо школьного курса, с которыми следует ознакомиться:

  1. основы теории чисел: остатки, теорема Эйлера, теоремы Ферма, Китайская теорема об остатках;
  2. матрицы: операции с матрицами, определитель, ранг, метод Гаусса;
  3. геометрия: геометрические преобразования, основы начертательной геометрии;
  4. комбинаторика: сочетания, перестановки, метод включения-исключения;
  5. теория вероятностей: понятие вероятности, базовые формулы.

Теоретическая подготовка: алгоритмы и структуры данных

Другая сторона теоретической подготовки – изучение существующих алгоритмов и структур данных. Конечно, здесь нужно изучать все гораздо подробнее и больше, чем в чистой математике, однако все равно нужно знать меру: редкие и/или сверхсложные алгоритмы практически никогда не пригодятся на олимпиадах – либо не будет задач на эту тему, либо время на их написание будет неоправданно длительным. Однако это не побуждение к их неизучению – чем больше алгоритмов вы знаете, тем лучше – кто знает, может когда-нибудь и пригодится. Будет очень полезно, как минимум, иметь о них представление.

Вот небольшой, далеко не полный список для начала:

  1. динамическое программирование;
  2. алгоритмы на графах (обходы, кратчайшие пути, стягивающие деревья, потоки, паросочетания, мосты, точки сочленения);
  3. геометрические алгоритмы (заметающая прямая, построение выпуклой оболочки, определение принадлежности точки многоугольнику и т.п.);
  4. алгоритмы на строках (поиск подстроки, префикс-функция, z-функция);
  5. простые математические алгоритмы (алгоритм Евклида, быстрое возведение в степень, нахождение простых чисел, разложение на множители);
  6. структуры данных (стек, очередь, двоичное дерево, сбалансированное двоичное дерево, дерево интервалов, дерево Фенвика, бор, суффиксное дерево, хэш-таблица).

Практическая подготовка: стандарты

Эта часть подготовки включает в себя тренировку навыков кодирования стандартных алгоритмов, про которые говорилось в предыдущих разделах. Эти алгоритмы во время соревнования не должны писаться в первый раз, так как сколь способным программистом вы бы ни были, в первый раз легко допустить ошибку, не учесть какой-то крайний случай, да и вообще, это долго. Они должны “отскакивать от пальцев”. Для этого необходимо все их проработать на тренировках, добиться того, чтобы код одного и того же алгоритма, написанный в разное время для разных задач, совпадал с точностью до имен переменных. Могу предложить такую схему заучивания алгоритма:

  1. изучить сам алгоритм, разобрать до мельчайших деталей;
  2. написать реализующий его код, строго следя за соответствием кода и алгоритма;
  3. удостовериться в правильности написанного кода, составив несколько тестов и написав менее эффективный, но более простой алгоритм;
  4. составить 20 или более тестов, как ручных так и случайных и сгенерить к ним ответы, используя уже написанные программы;
  5. раз в день в течение 1-2 недель вечером писать код алгоритма, стараясь каждый раз сохранять последовательность инструкций, циклов, названия переменных и т.п., и проверять его на составленных заранее тестах, причем подсматривать куда-то можно лишь первые 2-3 раза.

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

Практическая подготовка: языки и ООП

Одна из важнейших частей, про которую забывают многие олимпиадники, особенно школьники. Конечно, для достаточно успешного участия достаточно знать основы языка: типы данных, переменные, циклы и функции. Однако современные задачи часто гораздо удобнее и быстрее закодировать, если знать некоторые более глубокие особенности языка и основы ООП. Чем лучше вы знаете язык программирования, на котором пишете контесты, тем меньше у вас будет досадных ошибок при кодировании и тем лучше будут как внешние (читабельность), так и внутренние (скорость) характеристики кода.

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

Практическая подготовка: решение задач

Решение задач – самое главное направление подготовки. Без него изучение теории и получение практических навыков становится бессмысленной тратой времени. Решать нужно много. Даже когда нет возможности собраться командой – надо решать поодиночке. Сейчас существует довольно много онлайн-архивов с тысячами задач. Возможность прорешать все есть далеко не у многих, поэтому нужно стараться решать больше сложных и нестандартных задач – ведь именно такие задачи на реальном контесте, когда все остальные уже решены, определяют победителя. Однако про стандартные и простые задачи тоже не следует забывать – на контесте они должны решаться в первую очередь и очень быстро, так как именно скорость их сдачи может определить большую часть штрафного времени, что в конечном счете при спорных ситуациях пойдет вам на пользу. Поэтому некоторую часть времени нужно потратить и на них. Конечно здесь не имеются в виду задачи типа “A + B”.

Старайтесь также участвовать во всех онлайн-контестах, которых сможете. Это поможет прочувствовать дух соревнований, справиться с волнением, которое возникает у многих на реальном соревновании.

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

Список архивов, которые мне нравятся больше всего (на них немного задач, но большая часть из них достаточно интересна):

Из онлайн-соревнований:

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

Командная подготовка

Командная работа – именно то, что отличает ACM ICPC от других олимпиад типа IOI, TopCoder и т.д. Она совершенствуется только когда вы всей командой пишете контест, виртуальный или реальный. О взаимодействии внутри команды уже написано в нескольких статьях, которые приведены в конце, так что распыляться на эту тему не буду. Поделюсь лишь парой приемов командного программирования, которые не раз реально помогали:

1. парное написание кода – что-то вроде Extreme Programming, когда один член команды пишет код, а другой в следит за написанием и сразу же корректирует, если видит ошибку. Таким образом можно практически исключить возможность опечаток типа j вместо i и т.п. Это же поможет, если человек, хорошо и быстро пишущий код не совсем понимает само решение – второй будет ему подсказывать и направлять;

2. кодер + тестер – тесты составляются не тем, кто пишет код, а напарником, причем во время написания кода;

3. конвейер – хорошо помогает в начале контеста, когда есть несколько простых нерешенных задач. Кодер сдает подряд несколько задач, которые ему подсовывают сокомандники, объясняя условие, решение и сделав несколько тестов.

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

Заключение

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

В конечном счете все зависит только от вас. Если вы хотите добиться хороших результатов, нужно быть готовым пожертвовать свободным временем. Но не следует пропускать занятия в университете в пользу тренировок, по крайней мере, не все :) Многие предметы, в частности математика, дискретная математика, физика, начертательная геометрия и, естественно, все предметы, связанные с программированием, могут сослужить хорошую службу при решении задач (а остальные – для хорошего сна :) ).

На этом все. Готовьтесь, и удачи вам на предстоящих четвертьфиналах!

Что еще почитать:

Теоретический и практический минимум для участия в олимпиадах (И. Квасов)

О решении олимпиадных задач по программированию формата ACM ICPC (С.А. Оршанский, чемпион мира ACM ICPC 2004 г.)

Подготовка к школьным олимпиадам по информатике (Б. Маткаримов, тренер сборной Казахстана по IOI)