369A - Валера и тарелки

Будем действовать жадно. Пусть сейчас i-й день, и текущее блюдо типа 1. Тогда если у нас есть чистая глубокая тарелка, то воспользуемся ею. Иначе увеличим ответ. Если текущее блюдо типа 2, то мы сначала попробуем взять плоскую тарелку, а потом глубокую. Если чистых тарелок нет совсем, то увеличим ответ.

Авторское решение: 5306397

369B - Валера и олимпиада

В этой задаче требовалось найти такой массив a₁, a₂, ..., a_n, что верны условия:

1. r ≥ a₁ ≥ a₂ ≥ ... ≥ a_n ≥ l;
2. ;
3. ;

Понятно, что сумму s_k нужно распределить равномерно между первыми k элементами. Например, так:

remainder = (s_k mod k);
for(int i = 0; i < k; i++) 
{
	a_i = s_k / k + (remainder > 0);
	remainder = remainder - 1;
}

Если k ≠ n, то аналогично нужно поступить с остальными элементами, причем распределить им нужно s_all - s_k.

Многие не учитывали случай k = n, в результате получали RE11.

Авторское решение: 5306414

369C - Валера и выборы

Рассмотрим все дороги, которые нам нужно отремонтировать. Пометим их концы u, v белым цветом. После этого, посчитаем простую динамику d[v] (v — вершина в дереве) на дереве, которая для каждой вершины в дереве посчитает количество белых вершин в поддереве. Это просто посчитать примерно так c помощью рекурсивной функции calc(v, prev) (v — текущая вершина, а prev — ее непосредственный предок):

calc(v, prev)
{
	d[v] = 0; 
	if (white[v])
		dv += 1; 
	для всех u, таких что существует ребро (u,v) или (v,u) u != prev:
		calc(u, v);
		d[v] += d[u];  
}

После этого, добавим к ответу количество белых вершин v, для которых d[v] = 1

Авторское решение: 5306500

369D - Валера и дураки

Пусть p[A] — вероятность того, что дурак с номером A попадет, если совершит выстрел.

Заметим, что состояние очень просто описать парой чисел (A, B), где A — номер самого левого дурака, B — второго слева по порядку дурака. Понятно, что все дураки с индексами  ≥ B останутся живы. Выполним bfs по этим состояниям.

Состояние (0, 1) достижимо в любом случае, потому что оно изначально. Поэтому сразу положим его в очередь. Далее, из текущего состояния в очереди мы можем перейти максимум в три состояния:

1. (B + 1, B + 2) — только если p[A] > 0 и существует такой дурак с номером j ≥ B, у которого p[j] > 0.
2. (A, B + 1) — только если p[A] > 0 и не существует такой дурак с номером j ≥ B, у которого p[j] = 100.
3. (B, B + 1) — только если p[A] ≠ 100 и существует такой дурак с номером j ≥ B, у которого p[j] > 0.

После этого, достаточно посчитать количество состояний, расстояние до которых от (0, 1) не более чем k. Также нужно аккуратно учесть, что если остался один дурак, то он не совершает выстрелов.

Авторское решение: 5306516

369E - Валера и запросы

Давайте поддержим множество xs[y] — все отрезки, чьи правые границы в точности равны y. Теперь сведем нашу задачу к другой. Для каждого запроса посчитаем количество отрезков, которым не принадлежит ни одна точка. Пускай это значение v. Тогда ответ на запрос это n - v. Добавим к нашему запросу точки 0 и точку MV + 1, где MV = 1000000. Пусть точки запроса имеют вид x₁ < x₂... < x_n. Рассмотрим x_i и x_i + 1. Пусть p_i это количество отрезков которые лежат строго внутри x_i и x_i + 1. Тогда v = p₁ + p₂ + ... + p_n - 1. Чтобы найти значения p_i нужно поступить так. Рассмотрим все такие пары (x, x_i + 1) по всем запросам и сложим их во второе множество xQ[r] — все пары, у которых правая граница равна r. Тогда чтобы узнать значения p для пар (x_i, x_i + 1) будем перебирать по возрастанию правую границу. Дополнительно будем поддерживать дерево Фенвика, которое умеет делать  +  = 1 в точке, и брать сумму на префиксе. Пусть i — текущая правая граница. Тогда мы можем узнать значение p для всеx пар (l, r), у которых правая граница равна i (l, i). Пусть j левая граница пары. Тогда ответом для пары будет значение S - sum(j), где S — количество добавленных в дерево Фенвика левых границ, а sum(j) — сумма на префиксе j. После этого, для текущей координаты нужно рассмотреть все отрезки, в множестве xs[i]. Пусть j левая граница отрезка. Тогда нам нужно сделать  +  = 1 в точке j в нашем дереве Фенвика. Итого, общая сложность решения .

Авторское решение: 5306535