353A - Домино

Обозначим сумму чисел на верхних половинках костей за s₁, а сумму на нижних — s₂. Если изначально s₁ и s₂ четные, то ответ, очевидно, 0. Заметим, что если числа на обеих половинках кости одинаковой четности, то при повороте этой кости четность s₁ и s₂ не меняется. Если же четность чисел на половинках разная, то при повороте кости меняется четность как у s₁ так и у s₂. Из этого следует, что если s₁ и s₂ имеют разную четность, то ответ  - 1. Если же s₁ и s₂ нечетные, то нужно проверить, имеется ли в наборе кость с числами разной четности на половинках. Если имеется, то ответ 1, иначе ответ  - 1.

353B - Две кучки

Для краткости будем говорить, что в кучки раскладываются числа, нарисованные на кубиках, а не сами кубики.

Заметим, что ответ на задачу, это произведение количеств различных чисел в каждой из кучек. Предположим, что все заданные числа различны. В этом случае ответ равен n². Предположим теперь, что есть два одинаковых числа, а все остальные различны. Тогда, если мы их положим в разные кучки, то ответ будет равен n², а если в одну, то n·(n - 1). Очевидно, первый вариант даст большее произведение.

Рассуждая аналогичным образом, можно прийти к выводу, что нужно действовать следующим образом. Возьмем числа, которые встречаются больше одного раза, и закидаем по одному из них в разные кучки, остальные пока отложим в сторону. После этого числа, которые встречаются по одному разу раскидаем поровну в разные кучки. Затем, все числа, которые мы отложили в сторону раскидаем по кучкам произвольным образом.

353C - Найдите максимум

Рассмотрим старший бит числа m. Если он равен нулю, то во всех в n - 1-ой позиции будет стоять 0, а значит a_n - 1 никак не повлияет на ответ и мы можем выбросить его из набора и считать ответ для массива из n - 1 элемента.

Если же старший бит числа m равен 1, то a_n - 1 для некоторых x будет входить в f(x), а для некоторых — нет. Рассмотрим все x, при которых a_n - 1 не будет входить в f(x). Это, очевидно, . Среди таких x максимальное f(x), очевидно, будет достигаться при x = 2^n - 1 - 1. Попробуем улучшить ответ этим значением.

Теперь нам осталось рассмотреть , среди них найти максимальное f(x) и попробовать улучшить ответ этим значением. Заметим, что во всех таких x на (n - 1)-ой позиции находится 1, поэтому мы можем найти максимальное значение f(y) среди всех и прибавить к нему a_n - 1.

353D - Очередь

Заметим, что если несколько девочек стоит в самом начале очереди, то они никогда не будут двигаться, поэтому удалим их, и будем считать, что очередь начинается с мальчика. Также заметим, что относительный порядок девочек при движении не меняется. Посчитаем для каждой девочки момент времени t_i, начиная с которого она перестанет двигаться в очереди навсегда. Заметим, что для i-ой по порядку девочки t_i ≥ t_i - 1. Будем считать t_i в порядке слева направо. Посмотрим на какой позиции y_i в очереди будет находиться девочка, когда она закончит свое движение, и на какой позиции x_i она находится сейчас. Тогда этой девочке потребуется не менее x_i - y_i времени, чтобы добраться до своего места. Тогда если x_i - y_i > t_i - 1, то t_i = x_i - y_i. Рассмотрим, что произойдет при x_i - y_i ≤ t_i. В момент времени t_i - 1 (i - 1)-ая девочка будет находиться на позиции y_i, поэтому t_i ≥ t_i - 1 + 1. С другой стороны, рассмотрим последний момент времени p, когда i-ая девочка стоит непосредственно за (i - 1), но еще не на позиции y_i. После этого, в момент времени p + 1 (i - 1)-ая девочка меняется местами со стоящим перед ней мальчиком, а i-ая девочка остается на своей позиции. Затем с момента времени p + 2 до t_i - 1 обе девочки меняются местами с впереди стоящими мальчиками. А в момент времени t_i - 1 + 1 i-ая девочка наконец встает на свое конечное место. Отсюда следует, что в этом случае t_i = t_i - 1 + 1.

353E - Антицепь

Разобьем имеющийся граф на цепи. Цепью назовем максимальную по включению последовательность одинаково направленных ребер. Если в каждой такой цепи не менее 2 ребер, то ответ — это количество таких цепей.

Если же есть цепь в которой одно ребро (u, v), то переберем, какую из вершин, инцидентных этому ребру, мы возьмем в максимальную антицепь (также переберем вариант, когда не берем ни одной вершины). Пусть это вершина v. После этого, выкинем из рассмотрения данную вершину и все вершины, которые достижимы из v и из которых достижима v. После этого граф превратится в цепочку, на которой можно за линейное время динамическим программированием найти размер максимальной антицепи. Покажем, как это сделать.

Выпишем все вершины в цепочку и пронумеруем слева направо числами от 1 до k. После этого будем считать величину d_i — размер максимальной антицепи, среди вершин с номерами j ≥ i. Тогда, если i > k, то d_i = 0. Иначе мы можем пропустить i-ую вершину и улучшить величину d_i значением d_i + 1. Также мы можем попробовать взять i-ую вершину в ответ. В этом случае нужно пропустить все вершины, которые либо достижимы из i-ой, либо из которых достижима i-ая, взять ответ от следующей, прибавить к нему единицу и попробовать улучшить ответ.