Задачник Базовый курс EN

Ровно ноль градусов

префиксные суммы хеш-таблица подсчёт вариантов наука и физика

Дан ряд среднесуточных температур за n дней в десятых долях градуса и число k. Сколько есть периодов из подряд идущих дней, средняя температура которых ровно k/10 градуса? Период — от одного дня до всего ряда; разные периоды считаются отдельно, даже если они пересекаются.

Тесты со второго по четвёртый — среднесуточная температура Алматы за 1941–2025 годы (реанализ ERA5 через Open-Meteo): 31 046 дней, ровно ноль, десять и 8,7 градуса.

Вход

В первой строке n и k (1 ≤ n ≤ 2·10⁵, |k| ≤ 1000), во второй — n целых чисел, по модулю не больше 1000.

Выход

Одно число — количество периодов.

Примеры

Пример 1

Вход

7 0
-20 15 5 0 -10 10 0

Выход

Ограничения

Время · Python: 3000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 8 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Средняя ровно k — то же самое, что сумма отклонений от k равна нулю. Вычтите k из каждого дня. Что тогда можно сказать о префиксных суммах на концах такого периода?

2Идея

Пусть P[i] — сумма первых i отклонений t − k. Сумма отклонений за дни с i + 1 по j равна P[j] − P[i], и она нулевая ровно тогда, когда P[i] = P[j]. Значит, нужно посчитать пары равных префиксных сумм.

3Разбор

Идём по ряду и держим хеш-таблицу: сколько раз уже встречалась каждая префиксная сумма. Начинаем с суммы 0, встреченной один раз, — это пустое начало ряда. На каждом шаге новая сумма образует пару с каждой такой же суммой из прошлого: прибавляем к ответу её счётчик и увеличиваем его.

Проверка всех периодов через префиксные суммы — тоже верное решение, но периодов n(n + 1)/2: для настоящего ряда это 4,8·10⁸, для 2·10⁵ дней — 2·10¹⁰.

Ответ может быть огромным: если все дни ровно k (шестой тест), подходит каждый период, и их около 2·10¹⁰.

3+Решение

4Сложность

O(n) в среднем: по одной операции с хеш-таблицей на день. Память — O(n) на счётчики.

5Типичные ошибки

Забыть пустое начало. Без начальной суммы 0 теряются все периоды, которые начинаются с первого дня.
Считать в среднем, а не в суммах. Деление даёт дроби, и сравнение «среднее равно k/10» в числах с плавающей точкой может ошибиться. Сумма отклонений — целое число.
32-битный ответ. В шестом тесте ответ больше двух миллиардов.

Алгоритмы задачи

TEC Приём Префиксные суммы Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки. O(n) на построение, O(1) на запрос 2 задачи DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи