982A - Row
Из двух, описанных в условии правил, следует, что рассадка является максимальной тогда, когда в ней не встречаются две единички рядом или три нолика. Также необходимо аккуратно обработать концы данного ряда — надо проверить, что нельзя посадить человека на самый правый или самый левый стул.
982B - Bus of Characters
Заметим, что финальные пары интроверт-экстраверт определяются однозначно, а также, что с помощью стека, можно восстановить, какой экстраверт к какому интроверту подсядет (заметим, что нолики единички будут образовывать правильную скобочную последовательность). Тогда одним из решений может быть такое:
- Сортируем массив длин рядов по возрастанию
- Для каждого интроверта пишем номер очередного свободна ряда и добавляем его в стек
- Для каждого экстраверта пишем последнее число из стека и удаляем его оттуда
982C - Cut 'em all!
Заметим, что если есть какое-то ребро, которое можно удалить, то мы можем сделать это, без каких-либо последствий. Рассмотрим такое ребро, что в одном из полученных поддеревьев уже точно нельзя удалить больше, а его удаление возможно. Что произойдет, если мы его оставим в дереве? Относительно другого конца ребра четность поддерева не изменилась, что означает, что на дальнейшие удаления это ребро не повлияло. А значит, если мы его удалим, то ответ улучшится.
Отсюда следует жадное решение: в дфс-е насчитываем для каждой вершины размер поддерева, включая текущую вершину, и если он четен, то ребро в потомка (если он существует), можно удалить.
982D - Shark
Давайте посортируем массив и будем вставлять числа в порядке сортировки от меньшего к большему. Используя структуру данных "Система непересекающихся множеств" можно легко поддерживать информацию о текущем количестве отрезков, а также используя map внутри функции объединения, и информацию о текущих размерах отрезков (локаций). Тогда остается лишь обновлять ответ, когда это требуется.
982E - Billiard
Если симметрично отражать прямоугольник на плоскости относительно своих сторон, то новая траектория движения шара окажется куда проще. А именно — прямой. Одно из возможных решений такое:
- Если вектор направлен под углом в 90 градусов к осям, то пишем if-ы.
- Иначе поворачиваем поле таким образом, чтобы вектор удара стал (1, 1).
- Выписываем уравнение прямой движения шара: – 1·x + 1·y + С = 0. Если подставим изначальное положение шара, то найдем коэффициент C.
- Заметим, что в бессконечно замощенной плоскости координаты любой лузы представимы в виде (k1·n, k2·m).
- Подставим координаты лузы в уравнение прямой шара. Получается диофантово уравнение A·k1 + B·k2 = C. Оно разрешимо в случае, если C | gcd(A, B). В противном случае решений нет.
- Из всех решений данного диофантово уравнения нас интересует наименьшее на положительной полуоси.
- По найденным k1, k2 легко получить координаты соответствующей им лузе
- Повернуть поле обратно, если требуется.
982F - The Meeting Place Cannot Be Changed
Предположим, что решение существует, и будем искать решение исходя из этого предположения. В конце проверим найденное решение за линию, и если оно решением не является, то предположение было неверно.
Пусть решение существует. Значит пересечение всех циклов не пустое. Возьмём один любой цикл, который назовём главным. Можно представить его как окружность с направлением по часовой стрелке. Отметим на этой окружности все искомые вершины, принадлежащие всем циклам.
Рассмотрим только циклы, которые выходят из вершины главного цикла, приходят в какую-то вершину главного цикла, а дальше движутся по главному циклу и замыкаются. Если цикл выходит из главного цикла, то он должен на него вернуться где-то дальше по направлению главного цикла, при этом не перескакивая отмеченные вершины с ответом (иначе будет пустое пересечение, а мы предположили, что не пустое) (считаем, что если цикл вернулся не по главному циклу туда же, откуда вышел, то он совершил скачок длинной весь главный цикл, а не 0). От вершины, в которой рассматриваемый цикл возвращается на главный, до вершины, из которой он выходит с главного, проведём дугу в направлении главного цикла. Те вершины главного цикла, которые такая дуга не покрывает, заведомо не могут являться ответом. Пересечение всех рассмотренных циклов с главным определяется пересечением всех таких дуг.
Мы не рассмотрели только циклы, которые несколько раз выходят с главного и несколько раз возвращаются на главный цикл. Но пересечение такого цикла с главным циклом будет таким же, как если пересечь отдельные циклы между соседними выходом/возвратом. Поэтому такие сложные циклы можно не рассматривать.
Теперь нужно отметить все дуги между возвратом-выходом с главного цикла. Для этого будем запускать dfs из всех вершин главного цикла и пытаться вернуться на главный цикл как можно дальше (расстояние измеряется по количеству вершин главного цикла между выходом и возвратом). Как было отмечено выше, циклы, выходя и возвращаясь, не могут перескакивать ответ. Значит все dfs'ы, стартующие между границами ответов, стремятся к какой-то вершине главного цикла, которая является граничной в дуге с возможными ответами. Значит если в одном dfs'е мы выбрали самую удалённую вершину из нескольких вариантов, то в другом dfs'е рассматриваемые варианты не поменяются ролями, и старая самая удалённая вершина так и останется самой удалённой среди тех же вариантов в новом dfs'е. Значит можно запускать все dfs'ы с общим массивом used, в котором кэшировать самую удалённую вершину.
В итоге решение сводится к тому, чтобы найти главный цикл, отсортировать его вершины по направлению обхода, запустить из них из всех dfs’ы с общим массивом used’ов, между стартом и финишом всех dfs’ов отметить дуги и пересечь их все, на пересечении всех дуг взять ответ. Если после удаления вершины-ответа в графе не останется больше циклов, то это действительно ответ, а иначе предположение было не верно и ответа не существует.
