509A - Максимум в таблице
В этой задаче нужно было сделать то, что написано в условии: построить таблицу(двумерный массив) по указанным правилам и найти максимум в таблице.
Можно было заметить также, что максимальный элемент находится в правом нижнем углу.
Также проходило и просто решение рекурсией:
def elem(row, col):
if row == 1 or col == 1:
return 1
return elem(row - 1, col) + elem(row, col - 1)
Кроме того, можно было заметить в таблице Треугольник Паскаля и понять, что ответ — это
Готовил: riadwaw
Разбор от: riadwaw
509B - Раскраска шаров
Пусть найдутся две кучки, в которых количество камней отличается строго больше чем на k, тогда решения не существует:
Пусть теперь M = max ai ≤ min ai + k = m + k, покажем, как построить правильную раскраску:
- покрасим по m камней в каждой кучке в первый цвет
- в каждой кучке все оставшиеся камни покрасим в любые различные цвета(можно использовать первый еще один раз) (это можно сделать т.к осталось не более k камней.
Заметим, что 1-ый цвет встречается в каждой кучке m или m + 1 раз, а остальные цвета — 0 или 1 раз
Готовил: Kostroma
Разбор от: riadwaw
509C - Суммы цифр
Будем действовать жадно. На первом шаге найдём минимальное число b1 с суммой цифр a1. Далее, на i-м шаге найдём минимальное число bi с суммой цифр ai, которое больше чем bi - 1.
Почему это правильно? Поскольку b1 — минимальное число с суммой цифрой a1, то первое число не меньше чем b1. Далее по индукции: i-е число не меньше bi, поэтому (i + 1)-е число должно иметь сумму цифр ai + 1 и быть больше чем bi. Но минимальное такое число как раз bi + 1. Значит, построенный пример даёт оптимальное решение задачи.
Осталось научиться решать подзадачу: найти минимальное число с суммой цифр x, которое больше y. Она решается стандартным подходом: идем по цифрам числа y с младших разрядов и пытаемся увеличить соответствующую цифру (считаем, что каждое число содержит бесконечно много нулей слева от своей старшей цифры). Пусть справа осталось k цифр, тогда сумма этих k цифр может быть любым натуральным числом от 0 до 9k. Если получилось увеличить текущую цифру так, что при каком-то выборе цифр справа от неё получилась сумма x, то мы получили ответ. Заметим, что цифры справа от текущей позиции в таком случае нужно заполнять жадно с младших разрядов, каждый раз используя максимально возможную цифру — таким образом мы действительно получим минимальный ответ.
Оценим максимальную длину ответа, т.е. числа bn. Заметим, что если длина десятичной записи bi хотя бы 40, то в промежутке между 10k и 10k + 1, где k — наименьшее натуральное число, такое что 10k ≥ bi, есть числа со всеми суммами цифр от 1 до 9k. Так как все ai ≤ 300, то при в отрезке [10k, 10k + 1] есть любая из интересующих нас сумм цифр. Значит, при достижении 40-значного числа на каждом шаге количество цифр в десятичной записи bi увеличивается не более чем на 2, а значит итоговый ответ будет иметь десятичную записать не длиннее 640 цифр (еще немного подумав, можно понять, что эту оценку можно усилить до 340).
Значит, получаем решение за O(n·maxLen), где maxLen — максимальная длина ответа. Поскольку n ≤ 300, maxLen ≤ 640, такое решение с запасом проходит.
Готовил: Endagorion
Разбор от: Kostroma
509D - Восстановление чисел
Заметим, что если в корректном ответе ко всем bi добавить 1, а из всех ai вычесть 1 (и при необходимости добавив k), то ответ останется корректным. поэтому можно считать, что ai = 0, тогда из первой строки однозначно восстанавливаются bj, а по ним — ai (Можно пока разрешить им быть отрицательными, а потом добавить нужное число раз k). Теперь для любых i, j мы можем найти "ошибку" .
Если все ошибки нулевые — всё отлично, возьмем k достаточно большим и ответ будет автоматически корректным.
Для того, чтобы не нарушалось условие в клетке (i, j) необходимо и достаточно, чтобы ei, j делилось на k. Таким образом, k должно быть делителем gcdi, j(ei, j). При этом, k должно быть строго больше, чем все числа в таблице. Таким образом выгодно попытаться поставить k = gcdi, j(ei, j), что можно сделать, если k > maxi, j(wi, j). В противном случае ответа не существует.
Готовили: Kostroma, riadwaw
Разбор от: riadwaw
509E - Мелодичная песня
Посчитаем суммы vowel(si) на всех префиксах строки, чтобы за O(1) можно было легко посчитать сумму vowel(si) на любой подстроке.
Будем перебирать m с 1 до . При фиксированном m найдем сумму простых мелодичностей всех подстрок длины m. Для этого посмотрим, сколько раз i-й символ s входит в эту сумму.
При m = 1 каждый символ входит ровно один раз. При m = 2 все символы, кроме крайних — 2 раза, крайние 1 раз. При m = 3 все 3 раза, кроме второго и предпоследнего(2 раза) и первого и последнего (1 раз).
При m = |s| каждый символ входит один раз, как и в случае m = 1, а при m = |s| - 1— 2 раза кроме крайних, как и в случае m = 2.
В общем случае, i-й символ входит min(m, |s| - m + 1, i, |s| — i + 1) раз. Можно заметить, что при переходе от m к m + 1 к сумме прибавляются вхождения символов на подотрезке с m по |s| - m + 1(если m > |s| - m + 1, то убавляются на подотрезке с |s| - m + 1 по m).
Таким образом, можно легко пересчитать сумму вхождений гласных при переходе от m к m + 1, прибавив(убавив) сумму vowel на подстроке. Итоговое решение за O(N).
Готовил: zemen
Разбор от: zemen
509F - Контроль успеваемости
Рассмотрим произвольное дерево на n вершинах. Подвесим дерево за вершину 1, и пусть массив a — результат работы dfs-а. Тогда вершины поддерева с вершиной v, 1 ≤ v ≤ n, записаны в подмассив a[lv..lv + sizev - 1], где lv есть позиция вершины v в массиве, а sizev — размер поддерева.
Решим задачу, используя сей факт и ДП на подотрезках. Пусть задан массив a, и пусть e[l, r] есть количество деревьев, составленных из вершин a[l], a[l + 1], ..., a[r], т.ч. dfs, запущенный из вершины a[l], выведет вершины в том же порядке, в котором они представлены в массиве a. Тогда, если l = r, то e[l, r] = 1; иначе , где сумма берется по всем возможным множествам детей a[l], т.е. по всем таким k;pos1, ..., posk + 1, что l + 1 = pos1 < pos2 < ... < posk + 1 = r + 1, 1 ≤ k ≤ r - l, a[pos1] < a[pos2] < ... < a[posk] (вспомним, что в dfs-е дети перебираются в порядке возрастания). Однако даже при наличии ответов для подотрезков отрезка [1..n] решение с использованием такой формулы будет работать экспоненциально долго.
Финальная идея заключается во введении d[l, r]: = e[l - 1, r], 2 ≤ l ≤ r ≤ n. Действительно, из вышеприведенной формулы следует, что d[l, r] = ([утверждение] определим как 1, если утверждение истинно, и 0, если ложно), а также e[l, r] = d[l + 1, r]. Таким образом, d[l, r] и e[l, r] для каждого отрезка вычисляются за линейное время; ответом же на задачу является e[1, n]. Итоговая асимптотика решения O(n3).
Готовил: DPR-pavlin
Разбор от: DPR-pavlin