Практикум и контрольная №2

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

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

Признаки в условии:

• «сколько различных» — множество, одна строка;
• «самое частое» — словарь частот;
• «есть ли такое значение», причём в цикле — множество, иначе будет квадрат;
• «по возрастанию чего-то» — сортировка пар «признак и значение»;
• «сгруппировать по чему-то» — словарь, ключом признак.

Сегодня темы не подписаны, и рядом стоящие задачи почти никогда не про одно и то же.

Условие: «дан список из ста тысяч чисел и сто тысяч запросов; для каждого запроса ответьте, встречается ли значение в списке».

Что здесь нужно?

Собраны вместе, с признаком, по которому каждая узнаётся.

Строки

1. s[i + 1] на последнем шаге — string index out of range.
2. Результат метода потерян: s.replace(...) без присваивания. Программа выводит введённое.
3. Срез с перепутанными границами — молча даёт кусок не той длины.

Списки

4. Забытый int после split — сравнение идёт по алфавиту, "10" < "9".
5. b = a вместо копии — изменение через одно имя видно через другое.
6. sort там, где нужны исходные позиции.
7. [[0] * m] * n — все строки таблицы оказываются одной.

Структуры данных

8. Обращение к отсутствующему ключу — KeyError. Лечится get.
9. Обход словаря там, где нужен порядок из списка, или наоборот забытый sorted.
10. Печать множества напрямую — порядок непредсказуем.

Функции

11. print вместо return — снаружи получается None.
12. Рекурсия без базы или с двумя вызовами себя в шаге.

В этих модулях появился новый способ не пройти по времени: не медленный алгоритм, а неудачная структура.

Три случая, которые встречаются чаще всего:

• проверка in по списку внутри цикла — заменяется множеством;
• count или index внутри цикла по тому же списку — заменяется словарём частот;
• перебор всех пар там, где хватает одного прохода со словарём.

Во всех трёх случаях исправление занимает одну строку, а ускорение получается в тысячи раз. Поэтому при вердикте «превышено время» первым делом смотрите не на алгоритм, а на то, что стоит внутри цикла.

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

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

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

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

Задача: «даны список из $10^5$ чисел и $10^5$ запросов; для каждого запроса ответьте, встречается ли значение в списке».

Ученик написал:

n, q = map(int, input().split())
a = list(map(int, input().split()))
asks = list(map(int, input().split()))

for x in asks:
    if x in a:
        print("YES")
    else:
        print("NO")

Решение верное и короткое, но получает превышение времени. Объясните, сколько работы оно делает, почему замена одной строки всё меняет, и что именно изменится.