Антти Лааксонен - Олимпиадное программирование

from Springer
International Publishing AG. Russian-language edition copyright © 2017 by DMK Press. All
rights reserved.
Все права защищены. Любая часть этой книги не может быть воспроизведена в
какой бы то ни было форме и какими бы то ни было средствами без письменного разре­
шения владельцев авторских прав.
Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероят­
ность технических ошибок все равно существует, издательство не может гарантировать
абсолютную точность и правильность приводимых сведений. В связи с этим издатель­
ство не несет ответственности за возможные ошибки, связанные с использованием книги.
ISBN 978-3-319-72546-8 (англ.)
ISBN 978-5-97060-644-5 (рус.)


© Springer International Publishing AG, part of
Springer Nature 2017
© Оформление, перевод на русский язык,
издание, ДМК Пресс, 2018

Оглавление
От автора........................................................................................................................ 11
Вступительное слово Алексея Малеева, основателя Moscow Workshops ICPC......11
Отзыв Дмитрия Гришина, основателя Mail.Ru Group.............................................. 13
Благодарность от редакции........................................................................................ 13
Отзыв Нияза Нигматуллина, двукратного чемпиона мира
ACM ICPC 2012 и 2013 годов...................................................................................... 14
Предисловие.................................................................................................................. 15
Глава 1. Введение.......................................................................................................... 17
1.1. Что такое олимпиадное программирование?..................................................... 17

1.1.1. Соревнования по программированию......................................................................18
1.1.2. Рекомендации желающим поучаствовать................................................................19
1.2. Об этой книге.................................................................................................................... 19
1.3. Сборник задач CSES....................................................................................................... 21
1.4. Другие ресурсы................................................................................................................ 23

Глава 2.Техника программирования.......................................................................... 25
2.1. Языковые средства......................................................................................................... 25

2.1.1. Ввод и вывод........................................................................................................................26
2.1.2. Работа с числами................................................................................................................ 27
2.1.3. Сокращение кода...............................................................................................................30
2.2. Рекурсивные алгоритмы............................................................................................... 31
2.2.1. Порождение подмножеств.............................................................................................31
2.2.2. Порождение перестановок............................................................................................32
2.2.3. Перебор с возвратом........................................................................................................33
2.3. Поразрядные операции................................................................................................ 35
2.3.1. Поразрядные операции................................................................................................... 37
2.3.2. Представление множеств...............................................................................................39

Глава 3. Эффективность............................................................................................... 42
3.1. Временная сложность.................................................................................................... 42

3.1.1. Правила вычисления........................................................................................................42
3.1.2. Часто встречающиеся оценки временной сложности........................................45
3.1.3. Оценка эффективности....................................................................................................46
3.1.4. Формальные определения............................................................................................. 47
3.2. Примеры.............................................................................................................................. 48
3.2.1. Максимальная сумма подмассивов............................................................................48
3.2.2. Задача о двух ферзях.......................................................................................................50

Глава 4.Сортировка и поиск........................................................................................ 53
4.1. Алгоритмы сортировки.................................................................................................. 53

6

 Оглавление
4.1.1. Пузырьковая сортировка................................................................................................54
4.1.2. Сортировка слиянием.......................................................................................................55
4.1.3. Нижняя граница временной сложности сортировки..........................................56
4.1.4. Сортировка подсчетом..................................................................................................... 57
4.1.5. Сортировка на практике.................................................................................................. 57
4.2. Решение задач с применением сортировки........................................................ 60
4.2.1. Алгоритмы заметающей прямой..................................................................................60
4.2.2. Составление --">