Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

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

Revision ru7, by AGrigorii, 2018-05-18 22:31:29

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. Из всех решений данного диофантово уравнения нас интересует наименьшее на положительной полуоси.
  7. По найденным k1, k2 легко получить координаты соответствующей им лузе
  8. Повернуть поле обратно, если требуется.

982F - The Meeting Place Cannot Be Changed

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 Первая редакция (сохранено в черновиках)