Разбор задачи демо-варианта 2022 года
Немного исправим условие задачи, сделаем ее более универсальной.
Задача
Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна K. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.
Прежде чем разобраться в алгоритме решения данной задачи, необходимо вспомнить некоторые моменты из теории чисел. А именно, деление с остатком.
Любое число (
a) представимо в виде:
a = c * k + r, где
c - результат целочисленного деления числа
a на
k,
r - остаток от деления
a на
k. Если число
a делится на
k, то
r = 0.
Допустим, что сумма (
s1) некторых чисел не кратна
k. Запишем ее в виде
s1 = c1 * k + r1. Какое число из данной суммы надо убрать, чтобы сумма оставшихся чисел делилась на
k?
Представим число, которое будем убирать в виде
a = c * k + r.
Запишем разницу:
s2 = s1 - a = c1 * k + r1 - (c * k + r) = k * (c1 - c) + (r1 - r).
s2 = k * (c1 - c) + (r1 - r) - результат данного выражения будет делиться на
k в том случае, если
r1-r=0. Следовательно,
r1=r. Другими словами, сумма
s1 и число
a должны иметь один и тот же остаток при делении на
k.
Значит, в задаче нам необходимо найти некоторую подпоследовательность чисел, начинающуюся с первого элемента последовательно, у которой есть собственный префикс, сумма элементов которого при делении на k дает тот же остаток, что и сумма всех элементов подпоследовательности. При этом сумма элементов префикса должна быть минимальной, а сумма элементов подпоследовательности максимальной. Тогда их разница даст нам искомую максимальную сумму.
Сумма элементов будет минимальной, если в ней меньше всего элементов (т.к. в последовательности только натуральные числа), максимальной - если в ней больше всего элементов.
Алгоритм
1) При каждом новом считанном числе, увеличиваем сумму всех элементов последовательности (
s). Также необходимо посчитать, какой остаток от деления на
k будет иметь данная сумма:
r = s % k.
Для того, чтобы сумма
s делилась на
k необходимо из нее убрать сумму элементов собственного префикса, которая имеет тот же остаток при делении на
k, что и
s.
2) Если такого префикса нет, значит при считывании числа, мы получили данный префикс, и нужную последовательность определить не можем. Сохраним сумму данного префикса в массиве (
prefix[r]), его длину в другом массиве (
mn_size). Длина префикса равна номеру считанного числа (при счете с 1):
mn_size[r] = i + 1.
3) Если же такой префикс есть в массиве, то можем вычислить сумму искомой последовательности, как
s - prefix[s % k]. Длина такой последовательности будет равна
i - mn_size[n % k].
4) При вычислении искомой суммы, ее необходимо проверять на максимальное значение и, в случае равенства с максимальным значением, проверять длину, чтобы в результате она оказалась минимальной.
Попробуйте реализовать данный алгоритм самостоятельно.