Предположим, что защитники города активировали некоторое множество артефактов. Оптимальной стратегией для их врагов будет разрушать их в порядке увеличения bi. Действительно, цель врага – разрушить как можно больше артефактов. Нет смысла тратить много энергии на трудноуничтожимый артефакт, пока есть легкая цель.
Идея:Павел Кротков Реализация: Антон Банных Разбор: Антон Банных
После построения полного графа из 2n вершин, которыми являются программы, выполним поиск совершенного паросочетания, удовлетворяющего описанным условиям. Один из самых простых алгоритмов, решающих эту задачу и укладывающихся в ограничения по времени, опять же динамическое программирование, но уже по подмножествам. Пусть для каждого набора вершин размера не более, чем k, мы знаем ответ. В таком случае перебрав все такие наборы и добавив к каждому все возможные ребра, еще в нем не лежащие, мы сможем посчитать ответ для всех наборов размера не более, чем k + 2. Время работы алгоритма в этом случае составит O(n222n). ?
f[i][j] = max(f[i][j - 1], f[i - 1][j]), если a[i] ≠ b[j]
f[i][j] = max(f[i][j - 1], f[i - 1][j], f[i - 1][j - 1] + 1), если a[i] = b[j]
Нахождение LCS является известной задачей, приводящейся в качестве примера при изучении динамического программирования. Для нахождения длины LCS для каждой пары позиций в строках a и b считается функция f[i][j], означающая размер наибольшей существующей LCS для префиксов строк a и b длины i и j, соответственно. Пересчитывается эта функция по следующему правилу:
Итак, разберемся, за сколько тактов процессор выполняет две программы. Это значение равно сумме длин программ минус те команды, которые будут выполняться одновременно. А таких команд не больше, чем LCSa, b), где a и b — строки, описывающие программы, а LCS(Longest Common Subsequence, наибольшая общая подпоследовательность) — функция, находящая наибольшую общую подпоследовательность двух последовательностей.
Разобьем решение задачи на два этапа и рассмотрим каждый в отдельности. Первым этапом будет построение графа, вершинами которого являются все программы, которые нам необходимо выполнить. Граф будет взвешенным, и вес ребра между двумя программами равен количеству времени, которое процессор потратит на их совместное выполнение. Вторым же этапом решения будет нахождение в этом графе совершенного паросочетания, в котором вес максимального ребра минимизирован.
Идея: Федор Царев Реализация: Сергей Мельников, Павел Кротков, Андрей Комаров Разбор: Павел Кротков
Задача C. Процессор
Можно заметить, что если мы возьмём вектор, который дали трисолианцу на первый год рождения, и вычтем его из всех векторов истории жизни трисолианца, то после выкидывания этого вектора мы фактически получим некоторую историю жизни трисолианца, у которого сумма элементов последнего вектора равна n − (сумма элементов выкинутого вектора).
Идея: Аксёнов Виталик Реализация: Аксёнов Виталик Разбор: Аксёнов Виталик
Задача B. Трисолианцы
Для того чтобы узнать какая именно птица улетает, необходимо хранить еще один дек со всеми птицами, отсортированными по возрастанию начальной координаты. Так как относительный порядок птиц не меняется, зная сторону, с которой птица улетела, можно узнать, какая именно в начальной нумерации. В случае одновременного прихода двух птиц к концам провода, всё происходит так же, но деки местами не меняются.
Первой улетит или самая левая птица, идущая влево, или самая правая, идущая вправо. Пусть первой улетает птица, идущая влево, причем это произойдет через время t. Тогда все птицы, идущие влево, сдвинутся влево на t, а все идущие вправо — на t вправо. Затем, все птицы развернутся, то есть, эти два дека поменяются местами. Храня пары <дек; сколько надо добавить ко всем числам в нём>, за O(1) можно находить через какой время и в какую сторону улетит очередная птица.
Для решения заведём два дека — линейной структуры данных, позволяющей за O(1) удалять элементы из обоих концов. В первом деке будут находиться птицы, идущие вправо, в порядке возрастания координаты. Во втором будут птицы, идущие влево и тоже отсортированные по возрастанию координаты.
Сделаем важное замечание. Порядок птиц на проводе никогда не поменяется. Действительно, он мог бы поменяться только в те моменты, когда птицы сталкиваются. Но при столкновении обе птицы разворачиваются и, поэтому, их порядок не поменяется.
Идея:Аксёнов Виталик Реализация: Андрей Комаров Разбор: Андрей Комаров
Задача A. Злые птицы
Russian Code Cup — Раунд
Комментариев нет:
Отправить комментарий