Задача 175A - Robot Bicorn Attack

Переберем все возможные разбиения данной строки на 3 подстроки (например, перебрав пару индексов – конец первой подстроки и конец второй подстроки). Если при разбиении все три подстроки удовлетворяют ограничениям (не имеют ведущих нулей и соответствующие им числа не превосходят 1000000), то пытаемся обновить текущей ответ суммой чисел данных подстрок. Всего количество разбиений O(N^2), где N – длина исходной строки. Проверка одного разбиения осуществляется за O(N)

Задача 175B - Plane of Tanks: Pro

Для решения необходимо промоделировать действия описанные в условии. Для каждого игрока оставим наилучший результат и посчитаем общее количество игроков N. Далее для каждого игрока найдем количество игроков C, результат которых не лучше наилучшего результата рассматриваемого игрока (это можно сделать простым циклом по всем игрокам). Далее необходимо определить его категорию по числам C и N. Для избежания проблем с точностью можно воспользоваться следующим подходом:

• если C * 100 >= N * 99, то игрок относится к категории "pro"
• если C * 100 >= N * 90, то игрок — "hardcore"
• если C * 100 >= N * 80, то игрок — "average"
• если C * 100 >= N * 50, то игрок — "random"

В противном случае игрок "noob".

Задача 175C - Geometry Horse

Очевидно, что фигуры следует уничтожать в порядке возрастания их стоимости. Отсортируем типы фигур в порядке возрастания стоимости. Создадим два указателя – позиция i в массиве P (текущий множитель) и позиция j в массиве типов фигур. При этом будем поддерживать текущий ответ и количество фигур G, которое необходимо уничтожить для перехода к следующему множителю. Если на очередном шаге количество фигур F текущего типа не превосходит G, то к ответу следует прибавить F * (i + 1) * Сj, G уменьшить на F, а указатель j увеличить на 1. В противном случае, к ответу необходимо прибавить G * (i + 1) * Cj, F уменьшить на G, указатель i увеличить на 1 и задать G = Pi – P(i-1). Такие итерации нужно продолжать, пока мы не просмотрим весь массив типов фигур.

Задача 175D - Plane of Tanks: Duel

Сначала необходимо определить исход битвы, если хотя бы одна из вероятностей непробития равна 100%. Если Вася не пробивает вражеский танк с вероятностью 100%, то ответ на задачу – 0. В противном случае, если Васин танк не пробивают с вероятностью 100%, то ответ на задачу – 1. Далее будем считать, что вероятности непробития не превосходят 99%. Можно проверить, что вероятность того, что танк останется живым после D = 5000 выстрелов по нему, меньше 10^-6 (для любых значений урона, пробиваемости и количества очков жизни). Для каждого из двух танков посчитаем следующую динамику dp[i][j] — вероятность того, что у танка останется j очков жизни после i выстрелов по нему. dp[0][hp] = 1, где hp – начальное количество очков жизни танка. Далее, для пересчета строки dp[i+1] достаточно для каждого значения j в строке dp[i] перебрать урон, который нанесет (i+1)-й снаряд (с учетом возможного непробития) и обновить соответствующее значение строки (i+1):

dp[i + 1][max(0, j – x)] += dp[i][j] * (1 – p) / (r – l + 1)

где p – вероятность непробития, x – потенциальный урон снаряда. Пусть dpv – полученная таблица для танка Васи, dpe – для танка врага.Теперь можно найти вероятность, что танк врага будет убит i-м выстрелом танка Васи: pk[i] = dpe[i][0] – dpe[i-1][0]. Заметим, что победы Васи происходят следующим образом: Вася сделал (K — 1) выстрелов и не убил вражеский танк, при этом не умер и сам. После чего Вася произвел K-й выстрел и уничтожил врага. Переберем K и посчитаем вероятность победы Васи K-м выстрелом. Для этого найдем, сколько выстрелов T успеет произвести враг прежде чем Вася выстрелит K-й раз (здесь нам единственный раз в решении понадобится скорострельность орудий):

T = ((K – 1) * dtv + dte - 1) / dte

где dtv – время перезарядки танка Васи, dte – время перезарядки врага. Тогда вероятность победы будет равна (1 – dpv[T][0]) * pk[K]. Просуммировав такие вероятности для K от 1 до D мы получим ответ. Вычислительная сложность алгоритма при этом есть O(D * hp * (r – l)).

Задача 175E - Power Defence

Заметим, что если отразить позицию башню относительно прямой OX, то интервал на пути движения монстра, на котором будет действовать башня, не изменится. Таким образом, можно считать, что башни разрешено строить в точках (_x_, 1), не более двух в одной точке. Далее заметим, что если существует такая точка X, что как слева, так и справа от нее располжены башни, а в самой точке X башен нет, то абсциссы всех «правых» башен можно уменьшить на 1 и от этого ответ не ухудшится. Аналогично, можно считать, что не существует двух соседних точек, в каждой из которых стоит ровно по одной башне. Теперь легко проверить, что для построения оптимального решения нам достаточно 13 подряд идущих целых точек. Переберем позиции замедляющих башен. В худшем случае, способов расставить замедляющие башни на 13 точках будет порядка 200000. Пусть мы зафиксировали некоторое расположение замедляющих башен. Для каждой из оставшихся свободных точек (точки, в которые можно поставить две башни, раздваиваем) посчитаем, какой урон нанесет огненная или электрическая башня, расположенная в этой точке, и сохраним полученные числа в массиве d (_d_[k].f и d[k].e – урон огненной и электрической башнями в точке k соответственно). Полученный массив пар значений отсортируем в порядке убывания первого значения d[k].f. Тогда оптимальное расположение оставшихся башен можно найти при помощи динамического программирования. Обозначим за dp[i][j] – наибольший урон, который можно получить, если у нас осталось i огненных башен и j электрических. Обозначим за p следующую величину p = cf – i + ce – j – количество башен, которое мы уже расставили при данном состоянии динамики. Заметим, что если i = 0, то мы использовали первые p значений массива d и ответом будет сумма наибольших j элементов d[k].e, начиная с индекса p. Иначе, мы либо ставим одну огненную башню, либо одну электрическую в позицию p. Не ставить башню в позицию p невыгодно в силу уменьшения значения d[p].f. Тогда получаем:

dp[i][j] += max(dp[i - 1][j] + d[p].f, d[i][j – 1] + d[p].e)

Ответом при данном расположении будет значение dp[cf][ce], которое вычисляется за время O(cf * ce * log(ce))

Замечание1: перебор можно сократить почти в 2 раза в силу того, что любые две симметричные друг другу расстановки эквивалентны между собой и дадут одинаковый ответ, однако, при данных ограничениях эта оптимизация не является необходимой

Замечание2: формула снижения скорости монстра 1 / (K + 1) позволяет легко посчитать урон от башни при фиксированных позициях замедляющих башен – замедляющие башни можно рассматривать независимо друг от друга