Разбор итогового контеста и что дальше

Каждая задача разобрана по одной схеме: признак, идея, ловушка.

Признак идёт первым намеренно. Идею вы почти наверняка знаете — все двадцать задач стоят на приёмах этого курса, ничего нового в них нет. Трудность контеста была не в том, чтобы вспомнить бинарный поиск по ответу, а в том, чтобы опознать, что он здесь нужен, когда в условии про него ни слова.

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

Если контест ещё не решён — решите сначала. Разбор никуда не денется, а вот второй раз попробовать «с чистого листа» уже не выйдет.

1. Счастливый билет

Признак. Работа с отдельными цифрами и длина до миллиона.

Идея. Число здесь не число, а строка. Читаем как строку, складываем коды символов — один проход по каждой половине.

Ловушка. int(input()) на миллионе цифр Python осилит, но ведущие нули пропадут, а условие их прямо разрешает. Номер 0012 превратится в 12, длина станет нечётной, и половины разъедутся.

2. Один-единственный раз

Признак. Спрашивается «сколько различных», а алфавит маленький — 26 букв.

Идея. Счётчик на 26 ячеек и один проход. Дальше считаем, у скольких ячеек ровно единица.

Ловушка. Соблазн написать text.count(ch) для каждой буквы алфавита. Это 26 проходов по миллиону символов; здесь ещё пройдёт, но привычка плохая — на алфавите побольше такое решение уже не проходит.

3. Точка равновесия

Признак. Для каждой позиции нужна сумма всего, что левее, и всего, что правее.

Идея. Сумма справа получается вычитанием: общая минус левая минус сам элемент. Левую копим по ходу, пересчитывать нечего.

Ловушка. Считать сумму заново на каждой позиции. При $n = 10^6$ это $10^{12}$ операций — не «медленно», а никогда.

4. Очередь в буфете

Признак. Порядок выбираем мы, и вклад каждого в ответ зависит от того, сколько человек стоит после него.

Идея. Время обслуживания $t_i$ входит в ответ ровно столько раз, сколько человек стоит после $i$-го. Значит, дольше всех обслуживаемых — в конец очереди: сортировка по возрастанию.

Ловушка. Отсортировать по убыванию. Проверить себя дешевле, чем спорить: на входе 1 100000 порядок «сначала долгий» даёт 100000, а «сначала быстрый» — 1.

5. Пары для танца

Признак. Пары составляются по близости значений, каждый входит не более чем в одну.

Идея. После сортировки выгодно объединять соседей: если пару можно составить вообще, её можно составить из соседних по росту. Идём слева, взяли пару — шагнули на два, не взяли — на один.

Ловушка. Жадно искать каждому «первого подходящего» без сортировки. Тогда высокий заберёт себе того, кто был нужен другому, и одна пара потеряется.

6. Грузовик

Признак. Три приметы сразу: спрашивается «наименьшее $X$, при котором получится»; проверить конкретное $X$ легко, а найти его прямо — непонятно как; и ответ монотонен — если грузоподъёмности хватает, то большей хватит тем более.

Идея. Поиск по ответу. Проверка «уложимся ли в $d$ дней при грузоподъёмности $X$» — это жадный проход: грузим, пока влезает, не влезло — новый день.

Ловушка. Границы. Снизу — не ноль, а самый тяжёлый ящик: машина, которая не увозит даже его, не увезёт ничего, и жадная проверка на такой грузоподъёмности зациклится или соврёт.

7. Общая мерка

Признак. Слова «делит и то, и другое» и числа до $10^{12}$.

Идея. Общие делители $a$ и $b$ — это ровно делители их наибольшего общего делителя. Считаем НОД, потом перебираем его делители до корня, парами.

Ловушка. Перебирать до $\min(a, b)$, то есть до $10^{12}$. Перебор делителей идёт до корня — это миллион шагов вместо триллиона.

8. Один удар киркой

Признак. Кратчайший путь по клеткам — плюс ровно один особый ресурс, который можно потратить один раз за весь путь.

Идея. Состояние — не клетка, а пара: клетка и признак «кирка уже потрачена». Граф удваивается: из «не потрачена» в стену можно шагнуть, попав в «потрачена»; из «потрачена» — нельзя. Дальше обычный поиск в ширину, ответ — меньшее из двух расстояний до финиша.

Ловушка. Посчитать обычный кратчайший путь, а потом «подправить» его, сломав самую неудобную стену на нём. Не работает: выгодный удар может лежать на совсем другом маршруте, который без кирки вообще не проходим.

9. Призы по кругу

Признак. Знакомая «не бери двух соседей» — но по кругу, а не в ряд.

Идея. Первая и последняя тумбы соседи, значит вместе они не берутся никогда, значит хотя бы одна из них свободна. Отсюда два обычных прогона на ряду: без последней тумбы и без первой. Ответ — большее.

Ловушка. Посчитать как ряд, а потом вычесть случай, где взяты обе крайние. Вычитается не то: убрав этот случай, вы не получаете максимум по оставшимся — максимум мог достигаться только на нём.

10. Ничьи кратные

Признак. «Не делится ни на одно из $k$», причём $k \le 10$ — это $2^{10}$ подмножеств, — а $n$ до $10^{18}$, то есть перебирать числа исключено.

Идея. Формула включений и исключений. Кратных числу $m$ ровно $\lfloor n/m \rfloor$. Складываем по одиночкам, вычитаем по парам (там НОК), прибавляем по тройкам. Ответ — $n$ минус посчитанное.

Ловушка. Не оборвать счёт, когда НОК подмножества перескочил $n$. В Python переполнения нет, но НОК десяти девятизначных чисел — число под девяносто знаков, и вычислять их для всей тысячи подмножеств незачем: как только НОК превысил $n$, кратных ноль.

11. Сумма цифр под заказ

Признак. Диапазон всего до $10^6$.

Идея. Пройти по всем числам и у каждого посчитать сумму цифр. Семь миллионов операций — секунда.

Ловушка. Испугаться формулировки и полезть в динамику по цифрам, потратив полчаса на то, что решается пятью строками. Ограничения — часть условия, а не украшение: они прямо говорят, какое решение здесь ждут.

12. Тот же браслет

Признак. Циклический сдвиг: одна и та же запись, начатая с другого места.

Идея. Все сдвиги строки лежат внутри неё же, приписанной к себе. Значит, достаточно спросить, входит ли вторая строка в first + first.

Ловушка. Забыть про равенство длин. Строка ab входит в abcabc, но браслеты разные — проверку длин надо делать первой.

13. Самый широкий просвет

Признак. Сказано «соседние слева направо», а на вход приходят в произвольном порядке.

Идея. Отсортировать и пройти по парам соседей.

Ловушка. Единственная отметка: соседних пар нет, ответ 0. Такие вырожденные случаи стоит проверять до отправки — они почти всегда есть в тестах.

14. Разность ровно d

Признак. Пары с фиксированной разностью — то есть для каждого элемента известно, какого напарника искать.

Идея. Сложить всё в словарь «значение → сколько раз встречается». Для каждого значения посмотреть, сколько в словаре значений на $d$ больше, и перемножить.

Ловушка. $d = 0$ считается иначе. Там напарник ищется в своей же группе, и пар не $k \cdot k$, а $k(k-1)/2$: элемент не образует пару сам с собой, и каждая пара иначе посчитается дважды.

15. Расписание переговорной

Признак. Максимальное число непересекающихся отрезков.

Идея. Сортировать по правому концу и жадно брать, если начало позже занятого конца. Правый конец — то, что мешает будущим заявкам, и брать надо тот, который освобождает переговорную раньше всех.

Ловушка. Сортировать по левому концу или по длине. Оба варианта проваливаются на маленьких примерах, и один из них разобран ниже отдельно.

16. Цех

Признак. Тот же признак, что в грузовике: проверить время легко, найти прямо — трудно, монотонность очевидна.

Идея. Поиск по ответу на времени. За $T$ минут станок с временем $t$ сделает $\lfloor T/t \rfloor$ деталей; складываем по станкам и сравниваем с $n$.

Ловушка. Разделить работу между станками «по-честному», пропорционально скоростям. Оптимум так не получается: доли выходят дробными, а детали целые, и округление в любую сторону даёт не тот ответ.

17. Самый крупный сомножитель

Признак. Разложение числа до $10^{12}$.

Идея. Делить на $i$ от 2, пока делится, увеличивая $i$ до корня из текущего остатка. Что останется больше единицы — само простое и больше всех найденных.

Ловушка. Перебирать до $n$. И второе: забыть про остаток в конце — у числа $2 \cdot 999999999989$ все делители до корня маленькие, а ответ лежит именно в остатке.

18. Самый большой остров

Признак. Связность клеток по стороне.

Идея. Обход в ширину или в глубину из каждой ещё не посещённой клетки суши; размер компоненты — число посещённых за один запуск. Попутно держим максимум и счётчик, сколько раз он встретился.

Ловушка. Рекурсивный обход. На поле $500 \times 500$ сплошной суши глубина доходит до 250 000 при пределе рекурсии в 1000 — про это было занятие 41. И вторая: обновляя максимум, не забыть сбросить счётчик в единицу, а не увеличить его.

19. Витрина сувениров

Признак. Наборы, а не последовательности: «покупки, отличающиеся только порядком, считаются одной».

Идея. Динамика по сумме. Внешний цикл по видам сувениров, внутренний по сумме — тогда каждый вид рассматривается один раз и порядок не возникает.

Ловушка. Поменять циклы местами. Внешний цикл по сумме считает упорядоченные наборы, и ответ выйдет больше: пара «1 + 2» и «2 + 1» посчитается дважды. Это ровно тот случай, когда программа работает, ошибок не выдаёт, а отвечает не на тот вопрос.

20. Развозка по кварталам

Признак. Движение только вправо и вниз — значит, к моменту вычисления квартала оба, из которых в него въезжают, уже посчитаны.

Идея. Динамика по сетке, одна строка памяти: row[c] += row[c-1], перекрытый квартал обнуляет ячейку.

Ловушка. Задать первую строку и первый столбец единицами. Это верно только для города без перекрытий: за перекрытым кварталом в первой строке путей ноль. База должна считаться тем же переходом — про это было занятие 43.

Весь курс на одной странице — но не списком тем, а списком примет. Читая незнакомое условие, вы ищете именно их.

Две проверки перед тем, как писать

Первая — арифметика (занятие 28). Прикиньте число операций: $n$, $n \log n$, $n^2$? Миллиард операций Python не успеет; сто миллионов — на грани; десять миллионов — спокойно. Если прикидка не сходится, приём выбран не тот, и писать код рано.

Вторая — вырожденные случаи. Один элемент, ноль, все одинаковые, самое большое допустимое значение. Половина неудач на контестах — не незнание темы, а необработанная граница.

Новая задача, темы в условии нет:

«В магазине $n$ товаров с целыми ценами. Выберите несколько так, чтобы их суммарная цена была как можно ближе к $S$, но не превышала её. Ограничения: $n \le 100$, $S \le 10^5$.»

Какой приём здесь нужен?

В задаче дан ряд из $n = 2 \cdot 10^5$ чисел и $q = 2 \cdot 10^5$ запросов «сумма на отрезке».

Решение на каждый запрос честно складывает числа отрезка. Пусть средняя длина отрезка — $10^5$.

Сколько сложений сделает такое решение? Введите целое число.

Задача 15 из контеста: «дано $n$ заявок на переговорную, каждая занимает промежуток от $l_i$ до $r_i$; две заявки нельзя удовлетворить вместе, если промежутки пересекаются или касаются концами. Какое наибольшее число заявок можно удовлетворить?»

Ученик рассудил так: «чем короче заявка, тем меньше она мешает остальным, значит брать надо самые короткие». И написал:

n = int(input())
flat = list(map(int, input().split()))
segments = [(flat[2 * i], flat[2 * i + 1]) for i in range(n)]

segments.sort(key=lambda s: s[1] - s[0])

taken = []
for left, right in segments:
    if all(right < other_left or other_right < left for other_left, other_right in taken):
        taken.append((left, right))

print(len(taken))

Пересечение здесь проверяется правильно, касание концами тоже считается пересечением — как и требует условие. Решение проходит многие тесты, но не все.

Постройте вход, на котором оно ошибается, объясните, почему рассуждение «короткие мешают меньше» неверно, и скажите, по какому признаку надо сортировать и почему именно по нему.