анти. Guide to Competitive
 Скачать 2.39 Mb.
|
|
Глава 10. Алгоритмы на деревьях ........................................................................... 157 10.1. Базовые понятия ........................................................................................................ 157 10.1.1. Обход дерева ................................................................................................................ 158 8 Оглавление 10.1.2. Вычисление диаметра ............................................................................................... 159 10.1.3. Все максимальные пути ............................................................................................ 161 10.2. Запросы к деревьям ................................................................................................. 162 10.2.1. Нахождение предков ................................................................................................. 162 10.2.2. Поддеревья и пути ...................................................................................................... 163 10.2.3. Наименьшие общие предки .................................................................................... 165 10.2.4. Объединение структур данных .............................................................................. 168 10.3. Более сложные приемы ........................................................................................... 169 10.3.1. Центроидная декомпозиция ................................................................................... 170 10.3.2. Heavy-light декомпозиция ....................................................................................... 170 Глава 11. Математика ................................................................................................ 172 11.1. Теория чисел................................................................................................................. 172 11.1.1. Простые числа и разложение на простые множители ................................. 172 11.1.2. Решето Эратосфена ................................................................................................... 175 11.1.3. Алгоритм Евклида ........................................................................................................ 176 11.1.4. Возведение в степень по модулю ......................................................................... 178 11.1.5. Теорема Эйлера ............................................................................................................ 178 11.1.6. Решение уравнений в целых числах ................................................................... 180 11.2. Комбинаторика ........................................................................................................... 181 11.2.1. Биномиальные коэффициенты .............................................................................. 181 11.2.2. Числа Каталана ............................................................................................................. 184 11.2.3. Включение-исключение ........................................................................................... 186 11.2.4. Лемма Бёрнсайда ........................................................................................................ 188 11.2.5. Теорема Кэли ................................................................................................................. 189 11.3. Матрицы ......................................................................................................................... 190 11.3.1. Операции над матрицами ........................................................................................ 190 11.3.2. Линейные рекуррентные соотношения.............................................................. 192 11.3.3. Графы и матрицы ......................................................................................................... 194 11.3.4. Метод Гаусса .................................................................................................................. 196 11.4. Вероятность .................................................................................................................. 199 11.4.1. Операции с событиями ............................................................................................. 200 11.4.2. Случайные величины.................................................................................................. 201 11.4.3. Марковские цепи ......................................................................................................... 203 11.4.4. Рандомизированные алгоритмы ........................................................................... 205 11.5. Теория игр ..................................................................................................................... 207 11.5.1. Состояния игры .............................................................................................................. 207 11.5.2. Игра ним .......................................................................................................................... 209 11.5.3. Теорема Шпрага–Гранди .......................................................................................... 210 11.6. Преобразование Фурье ........................................................................................... 213 11.6.1. Работа с полиномами ................................................................................................. 213 11.6.2. Алгоритм БПФ ............................................................................................................... 214 11.6.3. Вычисление свертки .................................................................................................... 217 Глава 12. Дополнительные алгоритмы на графах ................................................ 219 12.1. Сильная связность...................................................................................................... 219 Оглавление 9 12.1.1. Алгоритм Косарайю .................................................................................................... 220 12.1.2. Задача 2-выполнимости ........................................................................................... 221 12.2. Полные пути ................................................................................................................. 223 12.2.1. Эйлеровы пути .............................................................................................................. 223 12.2.2. Гамильтоновы пути ...................................................................................................... 226 12.2.3. Применения ................................................................................................................... 226 12.3. Максимальные потоки ............................................................................................. 228 12.3.1. Алгоритм Форда–Фалкерсона .............................................................................. 229 12.3.2. Непересекающиеся пути .......................................................................................... 232 12.3.3. Максимальные паросочетания .............................................................................. 233 12.3.4. Покрытие путями ......................................................................................................... 235 12.4. Деревья поиска в глубину ...................................................................................... 237 12.4.1. Двусвязность .................................................................................................................. 238 12.4.2. Эйлеровы подграфы ................................................................................................... 239 12.5. Потоки минимальной стоимости ......................................................................... 240 12.5.1. Алгоритм путей минимальной стоимости .......................................................... 241 12.5.2. Паросочетания минимального веса ..................................................................... 243 12.5.3. Улучшение алгоритма ................................................................................................ 244 Глава 13. Геометрия ................................................................................................... 247 13.1. Технические средства в геометрии .................................................................... 247 13.1.1. Комплексные числа ..................................................................................................... 247 13.1.2. Точки и прямые ............................................................................................................. 249 13.1.3. Площадь многоугольника ......................................................................................... 252 13.1.4. Метрики ........................................................................................................................... 254 13.2. Алгоритмы на основе заметающей прямой .................................................... 256 13.2.1. Точки пересечения ...................................................................................................... 256 13.2.2. Задача о ближайшей паре точек ............................................................................ 257 13.2.3. Задача о выпуклой оболочке ................................................................................. 258 Глава 14. Алгоритмы работы со строками ............................................................. 260 14.1. Базовые методы ......................................................................................................... 260 14.1.1. Префиксное дерево .................................................................................................... 261 14.1.2. Динамическое программирование ...................................................................... 261 14.2. Хеширование строк ................................................................................................... 263 14.2.1. Полиномиальное хеширование ............................................................................. 263 14.2.2. Применения ................................................................................................................... 263 14.2.3. Коллизии и параметры .............................................................................................. 264 14.3. Z-алгоритм ..................................................................................................................... 266 14.3.1. Построение Z-массива ............................................................................................... 266 14.3.2. Применения ................................................................................................................... 268 14.4. Суффиксные массивы ............................................................................................... 269 14.4.1. Метод удвоения префикса ....................................................................................... 269 14.4.2. Поиск образцов ............................................................................................................ 270 14.4.3. LCP-массивы .................................................................................................................. 271 10 Оглавление 14.5. Строковые автоматы ................................................................................................. 272 14.5.1. Регулярные языки ........................................................................................................ 273 14.5.2. Автоматы для сопоставления с образцом ......................................................... 274 14.5.3. Суффиксные автоматы .............................................................................................. 276 Глава 15. Дополнительные темы ............................................................................. 279 15.1. Квадратный корень в алгоритмах ....................................................................... 279 15.1.1. Структуры данных ........................................................................................................ 279 15.1.2. Подалгоритмы ............................................................................................................... 281 15.1.3. Целые разбиения ......................................................................................................... 283 15.1.4. Алгоритм Мо .................................................................................................................. 285 15.2. И снова о деревьях отрезков ................................................................................ 286 15.2.1. Ленивое распространение ........................................................................................ 287 15.2.2. Динамические деревья ............................................................................................. 290 15.2.3. Структуры данных в вершинах .............................................................................. 292 15.2.4. Двумерные деревья .................................................................................................... 293 15.3. Дучи ................................................................................................................................. 294 15.3.1. Разбиение и слияние ................................................................................................. 295 15.3.2. Реализация ..................................................................................................................... 296 15.3.3. Дополнительные методы .......................................................................................... 298 15.4. Оптимизация динамического программирования ....................................... 298 15.4.1. Трюк с выпуклой оболочкой ................................................................................... 299 15.4.2. Оптимизация методом «разделяй и властвуй» ............................................... 301 15.4.3. Оптимизация Кнута..................................................................................................... 302 15.5. Методы перебора с возвратом ............................................................................ 303 15.5.1. Отсечение ветвей дерева поиска ......................................................................... 304 15.5.2. Эвристические функции............................................................................................ 306 15.6. Разное ............................................................................................................................. 308 15.6.1. Встреча в середине ..................................................................................................... 308 15.6.2. Подсчет подмножеств ................................................................................................ 309 15.6.3. Параллельный двоичный поиск ............................................................................ 310 15.6.4. Динамическая связность ........................................................................................... 312 Приложение. Сведения из математики .................................................................. 315 Формулы сумм ....................................................................................................................... 315 Множества ............................................................................................................................... 317 Математическая логика ..................................................................................................... 318 Функции .................................................................................................................................... 319 Логарифмы .............................................................................................................................. 319 Системы счисления .............................................................................................................. 320 Библиография ............................................................................................................ 321 Предметный указатель ............................................................................................. 323 От автора I hope this Russian edition of my book will be useful to future competitive programmers in Russia. I appreciate the competitive programming culture in Russia, especially the international training camps which are known for challenging and high-quality problems. Indeed,competitive programming is a way to learn algorithms together with people from different countries. It does not matter where you come from – everybody is interested in creating efficient algorithms, which is the core of computer science. Antti Laaksonen Я надеюсь, что русское издание моей книги будет полезно будущим спор- тивным программистам России. Я ценю российскую культуру олимпиад- ного программирования, а в особенности международные учебные кэмпы, которые известны своими сложными и интересными задачами. Так спор- тивное программирование объединяет людей из разных стран в изуче нии алгоритмов. Не важно, откуда вы, важна ваша заинтересованность в созда- нии эффективных алгоритмов, которые являются основой Computer Science. Антти Лааксонен Вступительное слово Алексея Малеева, основателя Moscow Workshops Про спортивное программирование в России знают мало. А между тем именно российские команды ежегодно выигрывают самое престижное ми- ровое соревнование по программированию для студентов – International Collegiate Programming Contest (ICPC). История участия студентов из рос- сийских вузов на старейшем чемпионате ICPC отсчитывается с далекого 1993 года. В 2000 году студенты Санкт-Петербургского государственного университета показали необычайный прогресс и впервые среди россий- ских команд вырвались в чемпионы мира. С этого года российские коман- ды завоевали 33 золотые медали. Для сравнения: студенты из Китая всего 13 раз удостаивались золота за этот период, европейские участники – 12, США – всего 7. В мире наиболее сильную подготовку демонстрируют рос- сийские, китайские команды, студенты из Азии и Польши. Секрет успеха наших команд во многом объясняется усиленными тре- нировками. Но важна система, в рамках которой происходит подготовка. И здесь именно России удалось выстроить сильную тренировочную струк- 12 Вступительное слово Алексея Малеева, основателя Moscow Workshops туру для олимпиадных программистов. Чемпионов готовят ведущие вузы страны, технические и не только: Университет ИТМО, Московский физи- ко-технический институт, Санкт-Петербургский государственный уни- верситет, Московский государственный университет им. М.В. Ломоносова, Уральский федеральный университет, Саратовский университет и др. Объединившись вместе, консорциум из вышеперечисленных вузов в 2012 году запустил первый глобальный проект по подготовке студентов к чемпионату по спортивному программированию на кампусе МФТИ – Moscow Workshops . В формате учебно-тренировочных сборов студенты решают контексты и разбирают их с лучшими тренерами. Важная компо- нента Moscow Workshops – это интернациональность. Кэмпы открывают свои двери для молодых участников всего мира, предлагая им не только учиться, но и путешествовать, расширять свой кругозор. На каж дом вор- кшопе участники обогащают свои знания о других странах – посещают экскурсии, знакомятся с местной культурой и людьми. Уровень подготовки воркшопов очень высокий. Можно сказать, что те, кто прошел обучение в Moscow Workshops и уcпешно прошел отбор на- чальных этапов ICPC, уже представляют элиту мира программирования. За этими ребятами охотятся крупнейшие IT-компании, они получают луч- шие предложения о работе. В 2016 году по образовательной франшизе мы запустили тренировоч- ный лагерь в Гродно (Западная Белоруссия). С тех пор мы открыли регу- лярно действующие площадки в Барселоне (Испания) и Коллам (Индия), а в этом году запускаем воркшоп в одном из самых восточных городов Рос- сии – во Владивостоке. На данный момент в сборах уже приняли участие команды 240 университетов из 60 стран Европы, Азии, Южной и Северной Америки, Африки и Австралии. В 2019 году 11 из 12 команд, завоевавших медали в финале чемпионата ICPC, принимали учас тие в подготовитель- ных сборах Moscow Workshops. Спортивное программирование – это самый перспективный интеллек- туальный вид спорта, который можно назвать шахматами будущего. Уже сейчас им увлекаются лучшие умы планеты, и число участников растет год от года. Рост популярности олимпиадного программирования поло- жительно влияет на другие сферы жизнедеятельности человека. Навыки быстрого решения сложнейших задач помогают сегодняшним студентам в будущем справляться с реальными проблемами человечества креативно и эффективно. В ходе соревнований ребята учатся справляться со сложными моральными и психологическими нагрузками. За это время у них выра- батывается навык управлять рисками, ведь, чтобы выйти в финал ICPC, нужно потратить около 5 лет. Не каждому это суждено. Стрессоустойчи- вость и нацеленность на результат – это те качества, которые необходимы технологическим предпринимателям для запуска собственных проектов. Система Moscow Workshops также включает онлайн-курсы на платфор- Отзыв Дмитрия Гришина, основателя Mail.Ru Group 13 ме Coursera и онлайн-чемпионаты Opencup.ru, а также сборы для школь- ников по подготовке к IOI – Moscow Workshops Juniors, что в совокупности дает любому студенту из любого уголка мира, вне зависимости от принад- лежности к ведущим мировым университетам, реализоваться в области алгоритмов и программирования. Студентов, которые горят желанием развиваться в программировании и «кодят», не замечая хода времени, мы ждем на кэмпах Moscow Workshops и желаем всегда стремиться к результатам, которые кажутся невозможны- ми. С уважением, Алексей Малеев, проректор МФТИ, основатель Moscow Workshops Отзыв Дмитрия Гришина, основателя Mail.Ru Group В мои студенческие годы всегда было много программирования, и я часто участвовал в различных олимпиадах, но только теперь понимаю, насколь- ко мне тогда не хватало подобной книги. Всем, кто стремится покорить олимп международных чемпионатов по программированию, она точно придется по вкусу и поможет на этом нелегком пути достижения цели. Мы в Mail.Ru Group тоже создали несколько чемпионатов по программи- рованию, которые за последние 7 лет стали популярны не только в России, но и далеко за рубежом – уже более 20 стран принимает участие и больше 175 тысяч человек соревновались в Russian Code Cup, VK Cup, Russian AI Cup, ML BootCamp и др. Уверен, что эта книга поможет и тем, кто собира- ется принять в них участие тоже. Дмитрий Гришин, основатель, соучредитель и председатель совета директоров Mail.Ru Group, основатель венчурного фонда Grishin Robotics Благодарность от редакции Редакция издательства «ДМК-Пресс» выражает огромную благодарность Центру развития ИТ-образования при Московском физико-техническом институте и лично его руководителю Алексею Малееву и Mail.Ru Group за помощь в подготовке выпуска этой книги и, конечно, за отличную подго- товку наших чемпионов по программированию. Отзыв Нияза Нигматуллина, двукратного чемпиона мира ACM ICPC 2012 и 2013 годов Эта книга помогает познакомиться с олимпиадным программированием. Она рассчитана больше на начинающих либо не очень опытных в этом деле читателей, чем на продвинутых. Здесь подробно описано, как про- ходят олимпиады, что требуется, в чем их цель. Рассказано, как нужно к ним готовиться, какие качества в себе вырабатывать и какие есть способы тренироваться. Подробно разобраны базовые темы, трюки и алгоритмы. Средние и сложные методы преподносятся без четких доказательств. При- сутствует много полезных олимпиадных «трюков», которые редко встре- чаются в научной литературе. Большая часть популярных алгоритмов и методов, используемых в решении задач на олимпиадах, упомянута в этой книге. К каждой теме автор приложил код на языке C++, что позволяет лучше понять описанное и увидеть способы реализации. Есть отдельная глава, в которой описываются те конструкции и библиотеки C++, которые часто используются на олимпиадах, и только те, которые необходимы: описы- ваются они без подробностей и большой теории, а только на том уровне, чтобы читатель смог ими воспользоваться. Если читатель хочет разобрать- ся в них подробнее, то следует почитать дополнительную информацию по языку из специальных источников. Кроме того, описанные инструменты языка C++ сравниваются на протяжении всей книги на эффективность и удобство использования на олимпиадах. В книге раскрыт уникальный опыт участников и тренеров олимпиадно- го программирования. По правилам этих соревнований в финалах нельзя участвовать более двух раз. За более чем сорокалетнюю историю этих чемпионатов всего шесть человек стали двукратными чемпионами мира, все из Санкт-Пе- тербурга. Четверо – из Университета ИТМО: Геннадий Короткевич, Нияз Нигматуллин, Евгений Капун и Михаил Кевер, и двое – из СПбГУ: Николай Дуров и Андрей Лопатин. Предисловие ко второму изданию Во второе издание книги добавлено несколько новых разделов, в которых рассматриваются темы повышенного уровня: вычисление преобразова- ния Фурье, нахождение потоков минимальной стоимости в графах и ис- пользование конечных автоматов в задачах о строках. Я благодарен Олли Матилайнену, который прочитал большую часть но- вого материала и высказал много полезных замечаний и предложений. Антти Лааксонен Хельсинки, Финляндия Февраль 2020 Предисловие к первому изданию Эта книга задумана как содержательное введение в современное олим- пиадное программирование. Предполагается, что читатель уже знаком с основами программирования, но опыт проектирования алгоритмов или участия в соревнованиях по программированию не обязателен. Поскольку в книге рассматривается широкий круг тем разной степени трудности, она будет полезна как начинающей, так и более искушенной аудитории. Соревнования по программированию имеют довольно долгую историю. Международные студенческие олимпиады по программированию (ICPC) для студентов университетов проводились уже в 1970-х годах, а первая Меж- дународная олимпиада по информатике для учащихся старших классов состоя лась в 1989 году. Ныне оба мероприятия стали регулярными и соби- рают множество участников со всего мира. В наши дни олимпиадное программирование популярно как никогда. Важную роль в его распространении сыграл интернет. Существует актив- ное сетевое сообщество увлеченных этим движением программистов, каж дую неделю проводятся различные соревнования. Одновременно рас- тет и трудность заданий. Технические приемы, которыми еще несколько лет назад владели лишь лучшие из лучших, стали стандартными инстру- ментами, известными многим. Своими корнями олимпиадное программирование уходит в научное исследование алгоритмов. Но если ученый приводит доказательство ра- ботоспособности своего алгоритма, то олимпиадный программист реали- зует алгоритм и подает его на вход системы оценивания результатов. Эта система прогоняет алгоритм через различные тесты, и если все они про- ходят, то решение принимается. Это важный элемент олимпиадного про- граммирования, который позволяет автоматически получить убедитель- ные аргументы в пользу правильности алгоритма. Вообще, олимпиадное программирование стало отличным способом изучения алгоритмов, т. к. от участника требуется спроектировать алгоритм, который действитель- но работает, а не ограничиваться наброском идей, может, правильных, а может, и нет. У олимпиадного программирования есть еще одно достоинство – кон- курсные задачи заставляют думать. В формулировках задач не бывает ни- какого жульничества, в отличие от многих курсов по алгоритмам, где вам предлагают решить красивую задачу, но только последнее предложение звучит, к примеру, так: «Подсказка: для решения задачи модифицируйте алгоритм Дейкстры». Ну, а дальше думать особенно нечего, поскольку по- Предисловие к первому изданию 17 ход к решению уже известен. В олимпиадном программировании так не бывает. У вас имеется полный комплект инструментов, а уж какими из них воспользоваться, решайте сами. Решение олимпиадных задач развивает навыки программирования и отладки. Обычно решение засчитывается, только если пройдены все тесты, поэтому программист, стремящийся к успеху, должен реализовывать алго- ритм без ошибок. Это умение высоко ценится в программной инженерии, так что неудивительно, что ИТ-компании проявляют интерес к имеющим опыт олимпиадного программирования. Чтобы стать хорошим олимпиадным программистом, нужно много вре- мени, зато на этом пути можно и многому научиться. Можете быть увере- ны, что, потратив время на чтение этой книги, решение задач и участие в различных соревнованиях, вы будете лучше понимать, как устроены алго- ритмы. Буду рад вашим отзывам. Вы можете писать мне по адресу ahslaaks@ cs.helsinki.fi Я благодарен многим людям, приславшим отзывы на черновые редакции этой книги. Они очень помогли сделать книгу лучше. Отдельное спасибо Микко Эрвасти (Mikko Ervasti), Яанне Юннила (Janne Junnila), Яанне Коккала (Janne Kokkala), Туукка Корхонену (Tuukka Korhonen), Патрику Остегярду (Patric Östergård) и Роопе Сальми (Roope Salmi), написавшим подробные рецензии на рукопись. Я также признателен Саймону Рису (Simon Rees) и Уэйну Уилеру (Wayne Wheeler) из издательства Springer за плодотворное сотрудничество в ходе подготовки книги к печати. Антти Лааксонен Хельсинки, Финляндия Октябрь, 2017 |