Разбор [B`-B] Яндекс кружка
algo_easyВсем привет, это НЕофициальный разбор от @algo_easy.
// @algo_easy - канал в telegram для спортпрогеров от спортпрогеров всероссников. Подписывайтесь и делитесь разбором с друзьями! Задавайте вопросы по разбору в комментариях)
Мы разберем весь отбор в Яндекс кружок, как и в прошлом году.
[B’-B] 1. Усиления
Решение: Для начала заметим:
1) что нам выгодно брать максимально много баффов(если нет, то давайте наберем еще баффы, ответ не уменьшится).
2) что нужно каждые баффы брать, начиная с максимальных(отдельно по двум массивам). Например, если мы решили взять n раз первый бафф и m раз второй бафф. Тогда среди баффов первого типа надо взять n наибольших и аналогично среди баффов второго типа.
Теперь переберем сколько первых баффов мы возьмем, тогда мы можем однозначно узнать сколько вторых мы возьмем(это k - (колво первых баффов)). Остается только при помощи заранее насчитанных преф-сумм посчитать сумму каждого баффа, а также по формуле посчитать что получится. Из всех возможных вариантов выберем максимум. Нужно быть аккуратными только с тем, что нельзя брать > m и меньше нуля баффов второго типа.
Асимптотика: O(x log x + y log y) от сортировки.
[B’-B] 2. Великая уравниловка
Решение: Давайте поддерживать miltiset и queue(очередь). Тогда на операцию talon(добавить человека с x монетами) будем добавлять в конец queue. На операции level(уравниловка) будем всех людей из очереди добавлять в multiset(при этом саму очередь чистим), а на mashinka если кто-то есть в мультисете, то брать из него первый элемент, а иначе из очереди. Если кому-то неочевидно, почему это работает, то приглашаю в комментарии :) А так хорошее задание для читателя.
Асимптотика: Заметим, что каждый человек пройдет только по 1 разу по queue и multiset, получается O(n log n)
[B’-B] 3. Слон и конь
Решение: Тут нужно использовать довольно стандартную технику. Будем делать dfs, пытаться заходить во все подряд вершины из нашей текущей вершины, если они не посещены. Когда заходим отмечаем вершину как посещенную и повторяем, а когда выходим из вершины, то снимаем пометку отмеченности. Каждый новый заход куда-то = новый путь. Получается такая рекурсия, которая, например, из вершины 1 заходит в 2, обходит там всё и выходит и посещает новую из вершины 1 и т д. Заметим, что это работает за примерно количество простых путей * максимальную степень вершины. Заметим, что как только мы нашли 10^6 путей, то надо прекратить все запуски dfs и вывести ответ.
Асимптотика: O(min(x, 10^6) * 10), что дает максимум O(10^7) операций.
[B’-B] 4. Бронзовый век
Решение: Напишем обычный рюкзак dp[i][j][k], где i - количество рассмотренных жил, j - сколько одного типа набрали(j <= a), k - сколько другого(k <= b). Тогда в dp будет сколько минимум жил нам нужно набрать чтобы получить такое. Проще всего писать это дп вперед. Давайте сделаем переход из i - 1 в i. Перебираем j, k, и если dp[i - 1][j][k] != INF, то есть мы можем набрать (j, k), то сделаем переход. Понятно, что рассматривая текущий i, мы либо берем его, либо нет. Если не берем, то понятно, что переход из dp[i - 1][j][k] в dp[i][j][k], то есть сделаем dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k]). А если берем i, то переход из dp[i - 1][j][k] в dp[i][j + c[i]][k + t[i]]. Но надо делать min(j + c[i], a) и min(k + t[i], b), потому что нас не интересует, если мы набрали больше a или b. То есть, например если j + c[i] > a, то для упрощения мы будем считать, что мы перешли не в j + c[i], а в A. Получается, если берем i, то переход dp[i][min(a, j + c[i])][min(b, k + t[i])] = min(dp[i][min(a, j + c[i])][min(k + t[i], b)], dp[i - 1][j][k] + 1). Ответ будет в dp[n][a][b].
Асимптотика: O(n * a * b)
[B’-B] 5. Просто, как ABC
Решение: Вообще для каждого запроса [L, R] хотелось бы написать бинпоиск по ответу. Напишем его, пусть мы щас смотрим, можем ли набрать mid 'a', mid 'c' и соответственно одну 'b', что будет a...abc...c. Заметим, что ашки нам хотелось бы переместить как можно левее, цешки как можно правее. Тогда давайте просто найдем такую наименьшую позицию j бинпоиском, что на отрезке [L, j] mid ашек. Аналогично найдем наибольшую k, что на отрезке [k, R] будет mid цешек. Тогда надо проверить, что на отрезке [j + 1, k - 1] есть хотя бы одна 'b' с помощью предпосчитанных префсумм. Если таких j или k не существует или, например, j > R(то есть на отрезке [L, R] всего ашек меньше mid), то отрезок [j + 1, k - 1] не надо чекать.
Асимптотика: O(q log^2 n)
[B’-B] 6. Оценка за курс
Решение: Стандартный подход в таких задачах (на максимизацию/минимизацию ответа при битовый операциях) это рассмотреть биты в порядке уменьшения/увеличения, тем самым выполняя что-то наподобие бинпоиска. Пусть мы хотим проверить, что можно набрать ответ x. (то есть сделаем бинпоиск с границами L = 0, R = 2^31, чтобы как бы перебирать биты в порядке от наибольшего к наименьшему). Тогда для всех чисел насчитаем сколько нужно в них добавить задач, чтобы все биты из x были включены. Это делается проходом по всем битам(от старшего к младшему) в числе. Если символы равны или в x ноль, а в a[i] единица, то просто скипаем. А если в x единица, а в числе a[i] ноль(пусть это бит i), то на самом деле ответ для числа это (x & (2^i - 1) минус (a[i] & (2 ^ i - 1)), так как нам без разницы на старшие биты, большие i, там все сходится. А в бите i в первый момент не сходится, поэтому мы прибавляем, чтоб получился бит i и все младшие биты. Тогда из таких подсчетов найдем k наименьших и проверим, что сумма их <=m. И обновим наши границы бинпоиска.
Асимптотика: O(n * 30 * 30).
Спасибо, что прочитали разбор! Остальные блоки будут разбираться в течении следующих несколько дней, подписывайтесь на @algo_easy :)