Разбор задачи демо-варианта 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) При вычислении искомой суммы, ее необходимо проверять на максимальное значение и, в случае равенства с максимальным значением, проверять длину, чтобы в результате она оказалась минимальной.
Попробуйте реализовать данный алгоритм самостоятельно.