Спортивное программирование [Стивен Халим] (pdf) читать онлайн

Стивен Халим, Феликс Халим

Спортивное программирование

Competitive
Programming 3
The New Lower Bound of Programming Contests

Steven Halim, Felix Halim

Спортивное
программирование
Новый нижний предел соревнований по программированию

Стивен Халим, Феликс Халим

Москва, 2020

УДК 004.02, 004.424
ББК 22.18
Х17

Х17

Халим С., Халим Ф.
Спортивное программирование / пер. с англ. Н. Б. Желновой, А. В. Снас­
тина. – М.: ДМК Пресс, 2020. – 604 с.: ил.
ISBN 978-5-97060-758-9
Книга содержит задачи по программированию, аналогичные тем, которые
используются на соревнованиях мирового уровня (в частности, ACM ICPC и IOI).
Помимо задач разного типа приводятся общие рекомендации для подготовки
к соревнованиям, касающиеся классификации заданий, анализа алгоритмов и пр.
Кроме стандартных тем (структуры данных и библиотеки, графы, математика,
вычислительная геометрия) авторы затрагивают и малораспространенные – им
посвящена отдельная глава.
В конце каждой главы приводятся краткие решения заданий, не помеченных
звездочкой, или даются подсказки к ним. Задания сложного уровня (помеченные
звездочкой) требуют самостоятельной проработки.
Издание адресовано читателям, которые готовятся к соревнованиям по про­
граммированию или просто любят решать задачи по информатике. Для изучения
материала требуются элементарные знания из области методологии програм­
мирования и знакомство хотя бы с одним из двух языков программирования –
C/C++ или Java.

УДК 004.02, 004.424
ББК 22.18

Russian­language edition copyright © 2020 by DMK Press. All rights reserved.
Все права защищены. Любая часть этой книги не может быть воспроизведена в ка­
кой бы то ни было форме и какими бы то ни было средствами без письменного разрешения
владельцев авторских прав.

ISBN 978­5­97060­758­9 (рус.)

© Steven Halim, Felix Halim, 2013
© Оформление, издание, перевод,
ДМК Пресс, 2020

Содержание
Вступление ................................................................................................................... 11
Предисловие ............................................................................................................... 13
От издательства ......................................................................................................... 27
Об авторах этой книги .......................................................................................... 28
Список сокращений ................................................................................................ 30
Глава 1. Введение ..................................................................................................... 32
1.1. Олимпиадное программирование....................................................................... 32
1.2. Как стать конкурентоспособным ......................................................................... 35
1.2.1. Совет 1: печатайте быстрее! .......................................................................... 36
1.2.2. Совет 2: быстро классифицируйте задачи ................................................. 37
1.2.3. Совет 3: проводите анализ алгоритмов ...................................................... 40
1.2.4. Совет 4: совершенствуйте свои знания языков
программирования .................................................................................................... 46
1.2.5. Совет 5: овладейте искусством тестирования кода ................................. 48
1.2.6. Совет 6: практикуйтесь и еще раз практикуйтесь! .................................. 52
1.2.7. Совет 7: организуйте командную работу (для ICPC) ............................... 53
1.3. Начинаем работу: простые задачи ...................................................................... 54
1.3.1. Общий анализ олимпиадной задачи по программированию .............. 54
1.3.2. Типичные процедуры ввода/вывода ........................................................... 55
1.3.3. Начинаем решать задачи ............................................................................... 57
1.4. Задачи Ad Hoc ........................................................................................................... 60
1.5. Решения упражнений, не помеченных звездочкой ........................................ 68
1.6. Примечания к главе 1.............................................................................................. 73

Глава 2. Структуры данных и библиотеки ................................................. 76
2.1. Общий обзор и мотивация ................................................................................... 76
2.2. Линейные структуры данных – встроенные библиотеки .............................. 79
2.3. Нелинейные структуры данных – встроенные библиотеки .......................... 90
2.4. Структуры данных с реализациями библиотек, написанными
авторами этой книги ...................................................................................................... 99
2.4.1. Граф ..................................................................................................................... 99
2.4.2. Система непересекающихся множеств......................................................103
2.4.3. Дерево отрезков...............................................................................................107
2.4.4. Дерево Фенвика ...............................................................................................112
2.5. Решения упражнений, не помеченных звездочкой .......................................118
2.6. Примечания к главе 2.............................................................................................121

6  Содержание

Глава 3. Некоторые способы решения задач.........................................124
3.1. Общий обзор и мотивация ...................................................................................124
3.2. Полный перебор ......................................................................................................125
3.2.1. Итеративный полный перебор ....................................................................127
3.2.2. Рекурсивный полный перебор (возвратная рекурсия) ..........................130
3.2.3. Советы ................................................................................................................134
3.3. «Разделяй и властвуй» ...........................................................................................146
3.3.1. Интересное использование двоичного поиска........................................146
3.4. «Жадные» алгоритмы ............................................................................................152
3.4.1. Примеры ............................................................................................................153
3.5. Динамическое программирование ....................................................................160
3.5.1. Примеры DP......................................................................................................161
3.5.2. Классические примеры ..................................................................................171
3.5.3. Неклассические примеры .............................................................................184
3.6. Решения упражнений, не помеченных звездочкой .......................................192
3.7. Примечания к главе 3 .............................................................................................195

Глава 4. Графы ...........................................................................................................197
4.1. Общий обзор и мотивация ...................................................................................197
4.2. Обход графа ..............................................................................................................198
4.2.1. Поиск в глубину (Depth First Search, DFS) ..................................................198
4.2.2. Поиск в ширину (Breadth First Search, BFS) ...............................................200
4.2.3. Поиск компонент связности (неориентированный граф) ....................202
4.2.4. Закрашивание – Маркировка/раскрашивание компонент
связности .....................................................................................................................203
4.2.5. Топологическая сортировка (направленный ациклический граф) ....204
4.2.6. Проверка двудольности графа .....................................................................206
4.2.7. Проверка свойств ребер графа через остовное дерево DFS ..................207
4.2.8. Нахождение точек сочленения и мостов (неориентированный
граф) ..............................................................................................................................209
4.2.9. Нахождение компонент сильной связности (ориентированный
граф) ..............................................................................................................................212
4.3. Минимальное остовное дерево ...........................................................................218
4.3.1. Обзор ..................................................................................................................218
4.3.2. Алгоритм Краскала .........................................................................................219
4.3.3. Алгоритм Прима ..............................................................................................221
4.3.4. Другие варианты применения .....................................................................222
4.4. Нахождение кратчайших путей из заданной вершины во все
остальные (Single – Source Shortest Paths, SSSP) .....................................................229
4.4.1. Обзор ..................................................................................................................229
4.4.2. SSSP на невзвешенном графе .......................................................................230
4.4.3. SSSP на взвешенном графе ...........................................................................232
4.4.4. SSSP на графе, имеющем цикл с отрицательным весом .......................237
4.5. Кратчайшие пути между всеми вершинами ....................................................242
4.5.1. Обзор ..................................................................................................................242
4.5.2. Объяснение алгоритма DP Флойда–Уоршелла.........................................243
4.5.3. Другие применения ........................................................................................246

Содержание  7
4.6. Поток ..........................................................................................................................253
4.6.1. Обзор ..................................................................................................................253
4.6.2. Метод Форда–Фалкерсона ............................................................................254
4.6.3. Алгоритм Эдмондса–Карпа ..........................................................................256
4.6.4. Моделирование графа потока – часть I......................................................257
4.6.5. Другие разновидности задач, использующих поток ..............................259
4.6.6. Моделирование графа потока – часть II ....................................................261
4.7. Специальные графы ...............................................................................................264
4.7.1. Направленный ациклический граф ............................................................265
4.7.2. Дерево .................................................................................................................274
4.7.3. Эйлеров граф ....................................................................................................276
4.7.4. Двудольный граф .................................................................................................277
4.8. Решения упражнений, не помеченных звездочкой .......................................287
4.9. Примечания к главе 4.............................................................................................291

Глаа 5. Математика .................................................................................................293
5.1. Общий обзор и мотивация ...................................................................................293
5.2. Задачи Ad Hoc и математика................................................................................294
5.3. Класс Java BigInteger ...............................................................................................303
5.3.1. Основные функции .........................................................................................303
5.3.2. Дополнительные функции ...........................................................................305
5.4. Комбинаторика........................................................................................................311
5.4.1. Числа Фибоначчи ............................................................................................311
5.4.2. Биномиальные коэффициенты ...................................................................312
5.4.3. Числа Каталана ................................................................................................313
5.5. Теория чисел.............................................................................................................319
5.5.1. Простые числа ..................................................................................................319
5.5.2. Наибольший общий делитель и наименьшее общее кратное..............322
5.5.3. Факториал .........................................................................................................322
5.5.4. Нахождение простых множителей с помощью
оптимизированных операций пробных разложений на множители ...........323
5.5.5. Работа с простыми множителями ...............................................................324
5.5.6. Функции, использующие простые множители ........................................325
5.5.7. Модифицированное «решето» .....................................................................327
5.5.8. Арифметические операции по модулю .....................................................327
5.5.9. Расширенный алгоритм Евклида:
решение линейного диофантова уравнения ......................................................328
5.6. Теория вероятностей..............................................................................................334
5.7. Поиск цикла ..............................................................................................................336
5.7.1. Решение(я), использующее(ие) эффективные структуры данных ......337
5.7.2. Алгоритм поиска цикла, реализованный Флойдом ................................337
5.8. Теория игр .................................................................................................................340
5.8.1. Дерево решений ..............................................................................................341
5.8.2. Знание математики и ускорение решения ...............................................342
5.8.3. Игра Ним ...........................................................................................................343
5.9. Решения упражнений, не помеченных звездочкой .......................................344
5.10. Примечания к главе 5 ..........................................................................................346

8  Содержание

Глава 6. Обработка строк ....................................................................................349
6.1. Обзор и мотивация .................................................................................................349
6.2. Основные приемы и принципы обработки строк ..........................................350
6.3. Специализированные задачи обработки строк ..............................................353
6.4. Поиск совпадений в строках ................................................................................360
6.4.1. Решения с использованием библиотечных функций ............................361
6.4.2. Алгоритм Кнута–Морриса–Пратта .............................................................361
6.4.3. Поиск совпадений в строках на двумерной сетке...................................364
6.5. Обработка строк с применением динамического программирования.....366
6.5.1. Регулирование строк (редакционное расстояние) ..................................366
6.5.2. Поиск наибольшей общей подпоследовательности ...............................369
6.5.3. Неклассические задачи обработки строк с применением
динамического программирования......................................................................370
6.6. Суффиксный бор, суффиксное дерево, суффиксный массив .......................372
6.6.1. Суффиксный бор и его приложения ...........................................................372
6.6.2. Суффиксное дерево.........................................................................................374
6.6.3. Практические приложения суффиксного дерева ....................................375
6.6.4. Суффиксный массив .......................................................................................379
6.6.5. Практические приложения суффиксного массива .................................386
6.7. Решения упражнений, не помеченных звездочкой........................................392
6.8. Примечания к главе ................................................................................................396

Глава 7. (Вычислительная) Геометрия ........................................................398
7.1. Обзор и мотивация .................................................................................................398
7.2. Основные геометрические объекты и библиотечные функции для них...400
7.2.1. Нульмерные объекты: точки .........................................................................400
7.2.2. Одномерные объекты: прямые ....................................................................403
7.2.3. Двумерные объекты: окружности ...............................................................408
7.2.4. Двумерные объекты: треугольники ............................................................411
7.2.5. Двумерные объекты: четырехугольники ...................................................414
7.2.6. Замечания о трехмерных объектах .............................................................415
7.3. Алгоритмы для многоугольников с использованием библиотечных
функций ............................................................................................................................418
7.3.1. Представление многоугольника ..................................................................419
7.3.2. Периметр многоугольника ............................................................................419
7.3.3. Площадь многоугольника..............................................................................420
7.3.4. Проверка многоугольника на выпуклость ................................................420
7.3.5. Проверка расположения точки внутри многоугольника .......................421
7.3.6. Разделение многоугольника с помощью прямой линии .......................422
7.3.7. Построение выпуклой оболочки множества точек..................................424
7.4. Решения упражнений, не помеченных звездочкой........................................430
7.5. Замечания к главе ...................................................................................................434

Глава 8. Более сложные темы .........................................................................436
8.1. Обзор и мотивация .................................................................................................436
8.2. Более эффективные методы поиска...................................................................436

Содержание  9
8.2.1. Метод поиска с возвратами с применением битовой маски ...............437
8.2.2. Поиск с возвратами с интенсивным отсечением ....................................442
8.2.3. Поиск в пространстве состояний с применением поиска
в ширину или алгоритма Дейкстры ......................................................................444
8.2.4. Встреча в середине (двунаправленный поиск) ........................................446
8.2.5. Поиск, основанный на имеющейся информации: A* и IDA* ................448
8.3. Более эффективные методы динамического программирования .............455
8.3.1. Динамическое программирование с использованием битовой
маски.............................................................................................................................455
8.3.2. Некоторые общие параметры (динамического
программирования) ..................................................................................................456
8.3.3. Обработка отрицательных значений параметров
с использованием метода смещения ....................................................................458
8.3.4. Превышение лимита памяти? Рассмотрим использование
сбалансированного бинарного дерева поиска как таблицы
запоминания состояний ..........................................................................................460
8.3.5. Превышение лимита памяти/времени? Используйте более
эффективное представление состояния ..............................................................460
8.3.6. Превышение лимита памяти/времени? Отбросим один параметр,
будем восстанавливать его по другим параметрам ..........................................462
8.4. Декомпозиция задачи............................................................................................467
8.4.1. Два компонента: бинарный поиск ответа и прочие ..............................468
8.4.2. Два компонента: использование статической задачи RSQ/RMQ ........470
8.4.3. Два компонента: предварительная обработка графа
и динамическое программирование ....................................................................471
8.4.4. Два компонента: использование графов ..................................................473
8.4.5. Два компонента: использование математики .........................................474
8.4.6. Два компонента: полный поиск и геометрия ..........................................474
8.4.7. Два компонента: использование эффективной структуры данных ...474
8.4.8. Три компонента ...............................................................................................475
8.5. Решения упражнений, не помеченных звездочкой .......................................484
8.6. Замечания к главе ...................................................................................................485

Глава 9. Малораспространенные темы ......................................................487
Общий обзор и мотивация...........................................................................................487
9.1. Задача 2­SAT .............................................................................................................488
9.2. Задача о картинной галерее .................................................................................491
9.3. Битоническая задача коммивояжера.................................................................492
9.4. Разбиение скобок на пары ....................................................................................495
9.5. Задача китайского почтальона ............................................................................496
9.6. Задача о паре ближайших точек..........................................................................497
9.7. Алгоритм Диница ....................................................................................................499
9.8. Формулы или теоремы...........................................................................................500
9.9. Алгоритм последовательного исключения переменных, или метод
Гаусса .................................................................................................................................502
9.10. Паросочетание в графах ......................................................................................505
9.11. Кратчайшее расстояние на сфере (ортодромия) ...........................................509

10  Содержание
9.12. Алгоритм Хопкрофта–Карпа..............................................................................511
9.13. Вершинно и реберно не пересекающиеся пути ............................................512
9.14. Количество инверсий ...........................................................................................513
9.15. Задача Иосифа Флавия ........................................................................................515
9.16. Ход коня ..................................................................................................................516
9.17. Алгоритм Косараджу ............................................................................................518
9.18. Наименьший общий предок ..............................................................................519
9.19. Создание магических квадратов (нечетной размерности) ........................522
9.20. Задача о порядке умножения матриц..............................................................523
9.21. Возведение матрицы в степень .........................................................................525
9.22. Задача о независимом множестве максимального веса .............................530
9.23. Максимальный поток минимальной стоимости ..........................................532
9.24. Минимальное покрытие путями в ориентированном
ациклическом графе ......................................................................................................533
9.25. Блинная сортировка .............................................................................................535
9.26. Ро­алгоритм Полларда для разложения на множители целых чисел ......538
9.27. Постфиксный калькулятор и преобразование выражений ........................540
9.28. Римские цифры .....................................................................................................543
9.29. k­я порядковая статистика .................................................................................545
9.30. Алгоритм ускоренного поиска кратчайшего пути .......................................549
9.31. Метод скользящего окна .....................................................................................550
9.32. Алгоритм сортировки с линейным временем работы.................................553
9.33. Структура данных «разреженная таблица» ....................................................555
9.34. Задача о ханойских башнях................................................................................558
9.35. Замечания к главе .................................................................................................559

Приложение А. uHunt ............................................................................................562
Приложение В. Благодарности .......................................................................567
Список используемой литературы ...............................................................569
Предметный указатель ........................................................................................574

Издательство «ДМК Пресс» выражает благодарность техническим редакторам
книги «Спортивное программирование», а именно:
 Олегу Христенко – главный судья Moscow Workshops; технический коор­
динатор Олимпиадных школ МФТИ, Moscow Workshops Juniors и между­
народных сборов по программированию для подготовки к соревновани­
ям по программированию; сопредседатель жюри Moscow Programming
Contest; соавтор курса «Быстрый старт в спортивное программирова­
ние» в рамках RuCode;
 Филиппу Руховичу – к.ф.­м.н.; преподаватель кафедры алгоритмов
и технологий программирования МФТИ; двукратный призер и победи­
тель Всероссийской олимпиады школьников по информатике; финалист
ACM ICPC 2014; четырехкратный призер NEERC (2010–2013); сотренер
бронзовых призеров ICPC 2019; методист отделения информатики лет­
них и зимних Олимпиадных школ МФТИ; соавтор курса «Быстрый старт
в спортивное программирование» в рамках RuCode;
 Владиславу Невструеву – преподаватель летних и зимних Олимпиад­
ных школ МФТИ, Летней компьютерной школы; преподаватель «От­
крытых Московских тренировок»; автор задач на олимпиады: «Ква­
лификационный этап Moscow Programming Contest», «Когнитивные
технологии», «Муниципальный этап Всероссийской олимпиады школь­
ников»; соавтор курса «Быстрый старт в спортивное программирование»
в рамках RuCode.

Коллеги из Национального университета Сингапура оказывают
значительное влияние на развитие сообщества олимпиадного про­
граммирования во всем мире. С молодым исследователем в области
компьютерных наук Стивеном Халимом и его коллегой профессором
Сан Теком мы в 2019 году провели сборы Discover Singapore в рамках
международного образовательного проекта Moscow Workshops, кото­
рый зародился 8 лет назад на кампусе Московского физико­технического института
(МФТИ). Сингапур в 2020 году готовился стать городом проведения международной
олимпиады школьников по информатике IOI. Хотя в планы вмешалась пандемия,
олимпиада все же пройдет в онлайн­режиме, а очно город примет IOI в 2021 году.
В России достаточно развито соревновательное программирование, популярны
олимпиады и чемпионаты на школьном и студенческом уровне. Благодаря высоким
достижениям российских студентов на международных соревнованиях по програм­
мированию, заявку на проведение чемпионата мира по программированию «ICPC
World Finals 2020» выиграла Москва, принимающим вузом стал МФТИ. Российские
студенты последние 20 лет уверенно доминируют на этом соревновании, а МФТИ –
единственный вуз в мире, который на сегодняшний день имеет непрерывную чере­
ду медалей ICPC ­ больше трех. Мы создали самый большой образовательный про­
ект в мире по алгоритмическому программированию Moscow Workshops, который
принес новые возможности более 3,5 тысячи студентов 61 страны. Независимым
критерием подтверждения их успехов становятся результаты на чемпионате ICPC
и старт карьеры в ведущих компаниях ИТ­индустрии.
На кампусе московского Физтеха с 2018 года проводится отбор и подготовка на­
циональной сборной на IOI. Также к этой олимпиаде школьников со всего мира мо­
гут подготовиться в школе Moscow Workshops Juniors. В 2019 году российская сборная
взяла 4 золотые медали IOI, трое из этих ребят учились в Juniors, как и еще 12 медали­
стов из сборных Беларуси, Азербайджана, Киргизии, Дании, Сирии, Турции, Болгарии
и Индии. Первые выпускники лагеря уже показывают выдающиеся успехи: в прошлом
году стартап AI Factory, созданный выпускником Juniors Александром Машрабовым
с напарниками, купила компания Snap за $166 млн. В 2020 году мы совместно с 10 рос­
сийскими вузами на принципах открытости, равенства, уважения, единства запустили
первый учебный фестиваль по алгоритмическому программированию и искусствен­
ному интеллекту RuCode для всех желающих попробовать свои силы. В рамках фести­
валя мы выпустили вводный онлайн­курс «Быстрый старт в спортивное программи­
рование» на платформе Stepik, провели интенсивы и чемпионаты по искусственному
интеллекту и алгоритмическому программированию. Мероприятия охватили 12 ты­
сяч человек, в том числе взрослых, и мы будем проводить фестиваль и дальше, чтобы
популяризировать ИТ­знания. RuCode был задуман так, чтобы сильные технические
вузы из разных регионов России смогли передать свои лучшие практики учащимся,
дать широкий спектр образовательных методик. Книга Стивена Халима – это тоже
экскурс, но в систему подготовки коллег с Востока, которые так же стабильно показы­
вают выдающиеся результаты на соревнованиях по программированию. Уверены, что
книга поможет изучить все самые необходимые алгоритмы и поднять ваш уровень
знаний в программировании до уровня чемпионов мира.
Алексей Малеев,
проректор МФТИ,
основатель международного образовательного проекта Moscow Workshops

На протяжении всего существования Mail.ru Group мы ставили пе­
ред собой амбициозные цели, главная из которых – стать центром
притяжения самых ярких талантов, способных генерировать новые
идеи, оставаясь при этом на стыке практики и академии.
Выиграть борьбу за таланты можно, только позволив каждому
участнику раскрыть свой потенциал, в том числе и в рамках чем­
пионатов. За почти 10 лет мы провели их больше 100, ориентируясь на ведущие
мировые практики. В процессе работы мы поняли, что конкуренция и соревнова­
тельный дух, вступающие в синергию с опытом и экспертизой, позволяют дости­
гать по­настоящему заметных высот.
Уверен, что книга «Спортивное программирование» Стивена Халима и Феликса
Халима поможет не только школьникам и студентам, поставившим перед собой
амбициозную цель добиться заметных результатов на международных олимпиа­
дах ICPC и IOI, но и всем тем, кто мечтает достичь новых профессиональных высот
и стать более конкурентоспособным при решении сложных IT­задач.
Желаю вам увлекательного чтения. Дерзайте!
Дмитрий Смыслов,
вице­президент по персоналу и образовательным проектам

Спортивное программирование в некотором роде определило мою
жизнь. Я увлекся разработкой еще на ZX Spectrum, позже принял
участие в школьной олимпиаде, задачи которой показались до­
вольно простыми... и не смог остановиться. Программирование
увлекло меня свободой, которую оно дает для выражения мыслей:
здесь практически нет рамок, и любую задумку можно реализовать
быстро и эффективно. Победа на олимпиадах помогла поступить на факультет ВМК
МГУ, а затем пройти путь от джуна­разработчика до руководителя отдела и совла­
дельца бизнеса.
Сейчас я издаю медиа Tproger. В комментариях мы часто сталкиваемся с мнени­
ем, что для работы спортивное программирование бесполезно: «в повседневной
жизни требуется решать задачи, которые никак не связаны с теми, что предлага­
ются на контестах вроде ICPC». Я не согласен.
Конечно, напрямую навыки спортивного программирования не помогут. Но
придумывание оптимальных алгоритмов, воспитание в себе внимания к деталям,
да хотя бы просто разминка для ума значительно упрощают достижение успехов
в карьере разработчика. Именно по этой причине я всегда с симпатией относился
к кандидатам, которые участвовали в олимпиадах по программированию или про­
сто нарешивали задачки из архивов. Везде есть исключения, но такие люди чаще
проектировали и реализовывали действительно хорошие продукты.
Готовы попробовать? Регистрируйтесь на любом сайте с архивом задач, берите
эту книгу в помощники, и вперед.
Если вы уже участвуете в контестах, то найдете в книге «Спортивное програм­
мирование» Стивена Халима и Феликса Халима много полезных техник и советов,
чтобы стать лучше.
И помните, если будет сложно – это нормально. Не останавливайтесь, только так
можно достичь настоящих высот в любом деле.
Алексей Михайлишин,
генеральный директор Tproger

Вступление
Однажды (это случилось 11 ноября 2003 года) я получил письмо по электрон­
ной почте, автор которого писал мне:
«Я должен сказать, что на сайте университета Вальядолида Вы положили
начало новой ЦИВИЛИЗАЦИИ. Своими книгами (он имел в виду «Зада­
чи по программированию: пособие по подготовке к олимпиадам по про­
граммированию» [60], написанное в соавторстве со Стивеном Скиеной)
Вы вдохновляете людей на подвиги. Желаю Вам долгих лет жизни, чтобы
служить человечеству, создавая новых супергероев – программистов».
Хотя это было явным преувеличением, письмо заставило меня задуматься.
У меня была мечта: создать сообщество вокруг проекта, который я начал как
часть моей преподавательской работы в университете Вальядолида. Я мечтал
создать сообщество, которое объединило бы множество людей с разных концов
света, связанных единой высокой целью. Выполнив несколько запросов в по­
исковике, я быстро нашел целое онлайн­сообщество, объединявшее несколько
сайтов, обладавших всем тем, чего не хватало сайту университета Вальядолида.
Сайт «Методы решения задач» Стивена Халима, молодого студента из Индо­
незии, показался мне одним из наиболее интересных. Я увидел, что однажды
мечта может стать реальностью, потому что на этом сайте я нашел результат
кропотливой работы гения в области алгоритмов и программирования. Более
того, цели, о которых он говорил, вполне соответствовали моей мечте: служить
человечеству. И еще я узнал, что у него есть брат, Феликс Халим, разделяющий
его увлечение программированием.
До начала нашего сотрудничества прошло довольно много времени, но,
к счастью, все мы продолжали параллельно работать над реализацией этой
мечты. Книга, которую вы сейчас держите в руках, является лучшим тому до­
казательством.
Я не могу представить лучшего дополнения для архива задач университета
Вальядолида. Эта книга использует множество примеров с сайта университета
Вальядолида, тщательно отобранных и разбитых по категориям по типам за­
дач и методам их решения. Она оказывает огромную помощь пользователям
данного сайта. Разобрав и решив большинство задач по программированию из
этой книги, читатель сможет легко решить не менее 500 задач, предложенных
«Онлайн­арбитром» университета Вальядолида, и попасть в число 400–500
лучших среди 100 000 пользователей «Онлайн­арбитра».
Книга «Спортивное программирование» также подходит для программи­
стов, которые хотят улучшить свои позиции на региональных и международ­
ных соревнованиях по программированию. Ее авторы прошли через эти сорев­
нования (ICPC и IOI) вначале как участники, а теперь и как тренеры. Она также
рекомендуется новичкам – как говорят Стивен и Феликс во введении: «Книгу
рекомендуется прочесть не один, а несколько раз».

16  Вступление
Кроме того, она содержит исходный код на C++, реализующий описанные
алгоритмы. Понимание задачи – это одно, знание алгоритма ее решения – дру­
гое, а правильная реализация решения через написание краткого и эффектив­
ного кода – третья непростая задача. Прочитав эту книгу трижды, вы поймете,
что ваши навыки программирования значительно улучшились и, что еще важ­
нее, вы стали более счастливым человеком, чем были раньше.
Мигель А. Ревилла,
Университет Вальядолида,
создатель сайта «Онлайн­арбитр»,
член Международного оргкомитета ICPC
http://uva.onlinejudge.org; http://livearchive.onlinejudge.org

Участники финального мирового турнира в Варшаве, 2012.
Слева направо: Фредерик Нимеля, Карлос, Мигель Ревилла, Мигель-младший, Феликс, Стивен

Предисловие
Эта книга обязательна к прочтению для каждого программиста, участвующего
в соревнованиях по программированию. Овладеть содержанием данной кни­
ги необходимо (но, возможно, недостаточно) для того, чтобы сделать шаг впе­
ред от простого обычного программиста до одного из лучших программистов
в мире.
Для кого написана эта книга:
 для студентов университетов, участвующих в ежегодных всемирных сту­
денческих соревнованиях по программированию ICPC [66] в качестве
участников региональных соревнований (включая финальные мировые
турниры);
 для учащихся средних или старших классов школ, принимающих учас­
тие в ежегодной Международной олимпиаде по информатике (IOI) [34]
(включая национальные или региональные олимпиады);
 для тренеров сборных команд по программированию, преподавателей
и наставников, которые ищут полноценные учебные материалы для сво­
их воспитанников [24];
 для всех, кто любит решать задачи по программированию. Для тех, кто
больше не имеет права участвовать в ICPC, проводятся многочисленные
состязания по программированию, в том числе TopCoder Open, Google
CodeJam, интернет­конкурс по решению задач (IPSC) и т. д.

Требования к уровню подгоТовки
Эта книга не предназначена для начинающих программистов. Она написана
для читателей, которые имеют хотя бы элементарные знания из области ме­
тодологии программирования, знакомы хотя бы с одним из двух языков про­
граммирования – C/C++ или Java (а еще лучше с обоими), освоили начальный
курс по структурам данных и алгоритмам (обычно он включается в программу
первого года обучения в университете для специальностей в области инфор­
матики) и знакомы с простым алгоритмическим анализом (по крайней мере,
им знакома нотация Big O). Третье издание было значительно переработано
и дополнено, так что эта книга также может быть использована в качестве дополнительного материала для начального курса по структурам данных и алгоритмам.

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

18  Предисловие
ниях, – мы понимаем, что для достижения этой цели требуется гораздо больше,
чем может дать данная книга. Для читателей, которые хотят большего, мы при­
водим дополнительные ссылки на полезные источники. Однако мы полагаем,
что после освоения содержания этой книги ваша команда будет чувствовать
себя намного увереннее в будущих состязаниях ICPC. Мы надеемся, что эта
книга послужит как источником вдохновения, так и стимулом к участию в со­
ревнованиях ICPC во время вашей учебы в университете.

учасТникам IOI
Большая часть наших советов для участников ACM ICPC пригодится и вам.
Программы ICPC и IOI в значительной мере схожи, однако IOI на данный мо­
мент исключает темы, перечисленные в табл. П1. Вы можете пропустить со­
ответствующие главы этой книги, отложив их до тех пор, пока не поступите
в университет (и не присоединитесь к команде этого университета, участвую­
щей в ICPC). Тем не менее полезно изучить эти методы заранее, так как допол­
нительные знания могут помочь вам в решении некоторых задач в IOI.
Мы знаем, что нельзя получить медаль IOI, просто основательно проштуди­
ровав эту книгу. Мы включили многие разделы программы IOI в данную книгу
и надеемся, что вы сможете добиться достойного результата на олимпиадах
IOI. Однако мы хорошо понимаем, что задачи, предлагаемые на IOI, требуют
сильных навыков решения задач и огромного творческого потенциала – тех
качеств, которые вы не сможете получить, только читая учебник. Книга может
дать вам знания, но в конечном итоге вы должны проделать огромную работу.
С практикой приходит опыт, а с опытом приходит навык. Так что продолжайте
практиковаться!

Преподавателям и наставникам  19

Слева направо: Дэниел, мистер Чонг, Раймонд, Стивен, Чжан Сюн, д-р Рональд, Чуанци

Таблица П1. Темы, не входящие в программу IOI [20]
Тема
Структуры данных: система непересекающихся множеств
Теория графов: нахождение компонентов сильной связности, поток
в сети, двудольные графы
Математические задачи: операции с очень большими числами
BigInteger, теория вероятностей, игра «Ним»
Обработка строк: суффиксные деревья и массивы
Более сложные темы: A*/IDA*
Нестандартные задачи

В этой книге:
Раздел 2.4.2
Разделы 4.2.1, 4.6.3,
4.7.4
Разделы 5.3, 5.6, 5.8
Раздел 6.6
Раздел 8.2
Глава 9

преподаваТелям и насТавникам
Эта книга используется как учебное пособие на курсе Стивена CS3233 «Олим­
пиадное программирование» в Школе программирования Национального уни­
верситета Сингапура. Продолжительность курса CS3233 составляет 13 учебных
недель, его примерная программа приведена в табл. П2. Слайды для этого кур­
са в формате PDF опубликованы на веб­сайте данной книги. Коллегам – препо­
давателям и наставникам рекомендуется изменять программу в соответствии
с потребностями студентов. В конце каждой главы данной книги приводятся
подсказки или краткие решения заданий, не помеченных звездочкой. Неко­
торые из помеченных заданий довольно сложны и не имеют ни ответов, ни
решений. Их можно использовать в качестве экзаменационных вопросов или
конкурсных заданий (разумеется, сначала нужно их решить).
Эта книга также применяется в качестве дополнительного материала
в программе курса CS2010 «Структуры данных и алгоритмы», в основном для
иллюстрации реализации нескольких алгоритмов и выполнения заданий по
программированию.

20  Предисловие
Таблица П2. Программа курса CS3233 «Олимпиадное программирование»
Неделя Тема
01
Введение
02
03
04
05
06
–
07
08
09
10
11
12
13

Структуры данных и библиотеки
Полный поиск, стратегия «разделяй и властвуй»,
«жадный» алгоритм
Динамическое программирование: основы
Динамическое программирование: техники
Командные соревнования в середине семестра
Перерыв в середине семестра (домашнее задание)
Графы, часть 1 (поток в сети)
Графы, часть 2 (поиск соответствий)
Математика (обзор)
Обработка строк (основные навыки, массив суффиксов)
(Вычислительная) Геометрия (библиотеки)
Более сложные темы
Заключительные командные соревнования

В этой книге:
Глава 1, разделы 2.2, 5.2,
6.2–6.3, 7.2
Глава 2
Разделы 3.2–3.4; 8.2
Разделы 3.5; 4.7.1
Разделы 5.4; 5.6; 6.5; 8.3
Главы 1–4; часть главы 9
Раздел 4.6; часть главы 9
Раздел 4.7.4; часть главы 9
Глава 5
Глава 6
Глава 7
Раздел 8.4; часть главы 9
Главы 1–9
(не ограничиваясь
только ими)

для курсов по сТрукТурам данных и алгориТмам
В этом издании содержание данной книги было переработано и дополнено та­
ким образом, что первые четыре главы книги стали более доступными для сту­
дентов первого курса, специализирующихся в области информатики и теории
вычислительных систем. Темы и упражнения, которые мы сочли относительно
сложными для начинающих, были перенесены в главы 8 и 9. Надеемся, что
студенты, только начинающие свой путь в области компьютерных наук, не ис­
пугаются трудностей, просматривая первые четыре главы.
Глава 2 была основательно переработана. Ранее раздел 2.2 представлял со­
бой просто список классических структур данных и их библиотек. В данном из­
дании мы расширили описание и добавили множество упражнений, чтобы эту
книгу можно было также использовать как пособие для курса по структурам
данных, особенно с точки зрения деталей реализации.
О четырех подходах к решению задач, обсуждаемых в главе 3 этой книги,
часто рассказывается в различных курсах по алгоритмам.
Текст предисловия также был переработан, чтобы помочь новым студентам
в области информатики ориентироваться в структуре книги.
Часть материала из главы 4 можно использовать в качестве дополнительной
литературы либо в качестве наглядного примера реализации. Этот материал
пригодится для повышения уровня знаний в области дискретной математики
[57, 15] или для начального курса по алгоритмам. Мы также представили новый
взгляд на методы динамического программирования как на алгоритмы, ис­
пользующие ориентированные ациклические графы. К сожалению, во многих
учебниках по компьютерным наукам такие темы до сих пор встречаются редко.

Принятые обозначения  21

всем чиТаТелям
Поскольку эта книга охватывает множество тем, обсуждаемых вначале более
поверхностно, затем более глубоко, ее рекомендуется прочитать не один, а не­
сколько раз. Книга содержит много упражнений (их около 238) и задач по про­
граммированию (их около 1675); практически в каждом разделе предлагаются
различные задания и упражнения. Вы можете сначала пропустить эти упраж­
нения, если решение слишком сложно или требует дополнительных знаний
и навыков, чтобы потом вернуться к ним после изучения следующих глав. Ре­
шение предложенных задач углубит понимание понятий, изложенных в этой
книге, поскольку они обычно включают интересные практические аспекты об­
суждаемой темы. Постарайтесь их решить – время, потраченное на это, точно
не будет потрачено впустую.
Мы считаем, что данная книга актуальна и будет интересна многим студен­
там университетов и старших классов. Олимпиады по программированию,
такие как ICPC и IOI, по крайней мере, еще много лет будут иметь похожую
программу. Новые поколения студентов должны стремиться понять и усвоить
элементарные знания из этой книги, прежде чем переходить к более серьез­
ным задачам. Однако слово «элементарные» может вводить в заблуждение –
пожалуйста, загляните в содержание, чтобы понять, что мы подразумеваем
под «элементарным».
Как ясно из названия этой книги, ее цель – развить навыки программиро­
вания и тем самым поднять уровень всемирных олимпиад по программиро­
ванию, таких как ICPC и IOI. Поскольку все больше участников осваивают ее
содержание, мы надеемся, что 2010 год (год, когда было опубликовано первое
издание этой книги) стал переломным моментом, знаменующим существен­
ное повышение стандартов соревнований по программированию. Мы наде­
емся помочь большему количеству команд справиться более чем с двумя (≥ 2)
задачами на будущих олимпиадах ICPC и позволить большему количеству
участников получить более высокие (≥ 200) баллы на будущих олимпиадах IOI.
Мы также надеемся, что многие тренеры ICPC и IOI во всем мире (особенно
в Юго­Восточной Азии) выберут эту книгу и оценят помощь, которую она ока­
зывает при выборе материала для подготовки к соревнованиям тем, без кого
студенты не могут обойтись на олимпиадах по программированию, – препо­
давателям и наставникам. Мы, ее авторы, будем очень рады, что нам удалось
внести свой вклад в распространение необходимых «элементарных» знаний
для олимпиадного программирования, поскольку в этом заключается основ­
ная цель нашейкниги.

приняТые обозначения
Эта книга содержит множество примеров кода на языке C/C++, а также отдель­
ные примеры кода на Java (в разделе 5.3). Все фрагменты кода, включенные
в книгу, выделяются моноширинным шрифтом.
Для кода на C/C++ в данной книге мы часто используем директивы typedef
и макросы – функции, которые обычно применяются программистами, участ­

22  Предисловие
вующими в соревнованиях, для удобства, краткости и скорости кодирования.
Однако мы не можем использовать аналогичные методы для Java, поскольку
они не содержат аналогичных функций. Вот несколько примеров наших со­
кращений для кода C/C++:
// Отключение некоторых предупреждений компилятора (только для пользователей VC++)
#define _CRT_SECURE_NO_DEPRECATE
// Сокращения, используемые для наиболее распространенных типов данных в олимпиадном
программировании
typedef long long
ll;
// комментарии, которые смешиваются с кодом,
typedef pair ii;
// выравниваются подобным образом
typedef vector
vii;
typedef vector
vi;
#define INF 1000000000
// 1 миллиард, что предпочтительнее, чем сокращение 2B,
// в алгоритме Флойда–Уоршелла
// Общие параметры memset
//memset(memo, – 1, sizeof memo);
// инициализация таблицы, сохраняющей значения
вычислений
// в динамическом программировании, значением – 1
//memset(arr, 0, sizeof arr);
// очистка массива целых чисел
// Мы отказались от использования "REP" and "TRvii" во втором и последующих
// изданиях, чтобы не запутывать программистов

Следующие сокращения часто используются как в примерах кода на C/C++,
так и в примерах кода на Java:
//
//
//
//
//
//
//
//

ans = a ? b : c;
// для упрощения: if (a) ans = b; else ans = c;
ans += val;
// для упрощения: ans = ans + val; и ее вариантов
index = (index + 1) % n;
// index++; if (index >= n) index = 0;
index = (index + n – 1) % n;
// index – – ; if (index < 0) index = n – 1;
int ans = (int)((double)d + 0.5);
// для округления до ближайшего целого
ans = min(ans, new_computation);
// сокращение min/max
альтернативная форма записи, не используемая в этой книге: ans