Разбор Codeforces #484 Round (Div. 2)

Revision ru6, by AGrigorii, 2018-05-18 22:29:24

982A - Row

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

982B - Bus of Characters

Заметим, что финальные пары интроверт-экстраверт определяются однозначно, а также, что с помощью стека, можно восстановить, какой экстраверт к какому интроверту подсядет (заметим, что нолики единички будут образовывать правильную скобочную последовательность). Тогда одним из решений может быть такое:

  1. Сортируем массив длин рядов по возрастанию
  2. Для каждого интроверта пишем номер очередного свободна ряда и добавляем его в стек
  3. Для каждого экстраверта пишем последнее число из стека и удаляем его оттуда

982C - Cut 'em all!

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

982D - Shark

Давайте посортируем массив и будем вставлять числа в порядке сортировки от меньшего к большему. Используя структуру данных "Система непересекающихся множеств" можно легко поддерживать информацию о текущем количестве отрезков, а также используя map внутри функции объединения, и информацию о текущих размерах отрезков (локаций). Тогда остается лишь обновлять ответ, когда это требуется.

982E - Billiard

Если симметрично отражать прямоугольник на плоскости относительно своих сторон, то новая траектория движения шара окажется куда проще. А именно — прямой. Одно из возможных решений такое:

  1. Если вектор направлен под углом в 90 градусов к осям, то пишем if-ы.
  2. Иначе поворачиваем поле таким образом, чтобы вектор удара стал (1, 1).
  3. Выписываем уравнение прямой движения шара —  – 1·x + 1·y + С = 0. Если подставим изначальное положение шара, то найдем коэффициент C.
  4. Заметим, что в бессконечно замощенной плоскости координаты любой лузы представимы в виде (k1·n, k2·m).
  5. Подставим координаты лузы в уравнение прямой шара. Получается диофантово уравнение A·k1 + B·k2 = C. Оно разрешимо в случае, если C | gcd(A, B). В противном случае решений нет.
  6. Из всех решений данного диофантово уравнения нас интересует наименьшее на положительной полуоси.
Tags round, 484, div2, edirorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English AGrigorii 2018-05-20 14:25:09 1558
en1 English AGrigorii 2018-05-20 14:20:09 5855 Initial revision for English translation
ru14 Russian AGrigorii 2018-05-18 22:38:03 0 (опубликовано)
ru13 Russian AGrigorii 2018-05-18 22:36:23 4 Мелкая правка: ' является <<максимальной>> тогда, ко' -> ' является максимальной тогда, ко'
ru12 Russian AGrigorii 2018-05-18 22:35:24 4
ru11 Russian AGrigorii 2018-05-18 22:34:38 1
ru10 Russian AGrigorii 2018-05-18 22:33:53 9
ru9 Russian AGrigorii 2018-05-18 22:33:26 2954
ru8 Russian AGrigorii 2018-05-18 22:31:49 20
ru7 Russian AGrigorii 2018-05-18 22:31:29 140
ru6 Russian AGrigorii 2018-05-18 22:29:24 8
ru5 Russian AGrigorii 2018-05-18 22:27:42 315
ru4 Russian AGrigorii 2018-05-18 22:21:46 645
ru3 Russian AGrigorii 2018-05-18 22:12:31 423
ru2 Russian AGrigorii 2018-05-18 22:08:00 932
ru1 Russian AGrigorii 2018-05-18 21:43:27 967 Первая редакция (сохранено в черновиках)