Нужные библеотеки

Библиотеки по фану полезно для cp

Xaydarov Zafar AlamovichPRO 25 Oktabr 2026 · 8 daqiqa o‘qish 2 0

Ниже собран полный рабочий справочник по всем необходимым инструментам для Competitive Programming (CP) на Python: их методы, временная сложность (O) и боевые примеры применения.

---

# 1. collections.deque (Двусторонняя очередь)
Обычный list при операциях слева (list.pop(0), list.insert(0, v)) работает за O(N), приводя к TLE. deque выполняет обе операции за O(1).

Основные функции и сложность:

dq.append(x) — добавить в правый конец: O(1)
dq.appendleft(x) — добавить в левый конец: O(1)
dq.pop() — извлечь и вернуть элемент справа: O(1)
dq.popleft() — извлечь и вернуть элемент слева: O(1)
dq.rotate(k) — циклический сдвиг на k шагов вправо (если k < 0 — влево): O(k)
deque(..., maxlen=K) — очередь фиксированной длины (вытесняет старые элементы при переполнении).

Применение в CP: Алгоритм 0-1 BFS

Если в графе веса рёбер равны только 0 или 1, Дейкстра с кучей за O(E \log V) не нужна — с deque задача решается за линейные O(V + E).

from collections import deque

def zero_one_bfs(start, adj, n):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    dq = deque([start])

    while dq:
        u = dq.popleft()
        for v, weight in adj[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                if weight == 0:
                    dq.appendleft(v)  # Ребро весом 0 — в приоритете (в начало)
                else:
                    dq.append(v)      # Ребро весом 1 — в конец очереди
    return dist

---

# 2. collections.defaultdict (Словарь по умолчанию)
Автоматически инициализирует отсутствующие ключи с помощью фабричной функции.

Основные фабрики:

defaultdict(list) — для списков смежности и группировок.
defaultdict(int) — для подсчёта частот (по умолчанию значение 0).
defaultdict(set) — когда нужно хранить только уникальные связи.
defaultdict(lambda: default_val) — любое начальное значение (например, \infty).

Применение в CP: Граф и ДП на разреженных состояниях

from collections import defaultdict

# 1. Граф с весами (не зная заранее размерность вершин)
adj = defaultdict(list)
edges = [(1, 2, 5), (1, 3, 2), (2, 4, 1)]
for u, v, w in edges:
    adj[u].append((v, w))

# 2. Динамическое программирование (по умолчанию inf)
dp = defaultdict(lambda: float('inf'))
dp[0] = 0

---

# 3. collections.Counter (Мультимножество / Счётчик)
Подкласс dict, оптимизированный под подсчет частот.

Основные функции и сложность:

Counter(iterable) — подсчет всех элементов: O(N)
c[key] — возвращает 0, если ключа нет (не вызывает KeyError): O(1)
c.most_common(k) — k самых частых элементов: O(N \log k)
c1 + c2, c1 - c2 — сложение и вычитание мультимножеств: O(\text{размер})
c1 & c2, c1 | c2 — минимум (пересечение) и максимум (объединение) кратностей.

Применение в CP: Проверка подстроки-анаграммы (Sliding Window)

from collections import Counter

s = "cbaebabacd"
p = "abc"

p_count = Counter(p)
window_count = Counter(s[:len(p)])
ans = []

if window_count == p_count:
    ans.append(0)

# Двигаем скользящее окно
for i in range(len(p), len(s)):
    window_count[s[i]] += 1
    left_char = s[i - len(p)]
    window_count[left_char] -= 1
    if window_count[left_char] == 0:
        del window_count[left_char] # Важно удалять, чтобы работало сравнение ==

    if window_count == p_count:
        ans.append(i - len(p) + 1)

print(ans)  # Индексы начал вхождений: [0, 6]

---

# 4. heapq (Куча / Очередь с приоритетами)
Модуль работает поверх обычного питоновского списка. **По умолчанию реализует Min-Heap (наименьший элемент всегда на вершине: h[0]).**

Основные функции и сложность:

heapq.heapify(arr) — превратить обычный массив в кучу на месте: O(N) (не O(N \log N)!)
heapq.heappush(heap, item) — положить элемент в кучу: O(\log N)
heapq.heappop(heap) — извлечь и вернуть минимальный: O(\log N)
heapq.heappushpop(heap, item) — сначала положить, затем вынуть минимум (быстрее раздельных вызовов): O(\log N)
heapq.heapreplace(heap, item) — сначала вынуть минимум, затем положить (быстрее): O(\log N)

Применение в CP: Max-Heap и жадные алгоритмы

Чтобы получить Max-Heap (максимальную кучу), умножайте значения на -1:

import heapq

# Задача: Всегда брать максимальный доступный элемент
tasks = [10, 40, 20, 5]
max_heap = [-x for x in tasks]
heapq.heapify(max_heap)  # O(N)

top = -heapq.heappop(max_heap) # 40
print(top)

# Если элементы состоят из нескольких полей:
# heapq сортирует кортежи лексикографически по первому элементу: (приоритет, значение)
pq = []
heapq.heappush(pq, (1, 'низкий'))
heapq.heappush(pq, (0, 'высокий'))
print(heapq.heappop(pq)[1]) # 'высокий'

---

# 5. bisect (Бинарный поиск)
Работает строго по отсортированным массивам за O(\log N). Избавляет от написания условий while left <= right и ошибок на границах \pm 1.

Основные функции:

bisect_left(arr, x) — находит индекс первого элемента, который \ge x (аналог std::lower_bound в C++).
bisect_right(arr, x) — находит индекс первого элемента, который > x (аналог std::upper_bound в C++).
Аргумент key — функция для поиска по составным объектам.

Важно: Функции insort_left и insort_right вставляют элемент в массив, но так как вставка в середину списка — это O(N), их использование в цикле приведёт к O(N^2) и TLE.

Применение в CP: Подсчет элементов на отрезке [L, R] за O(\log N)

from bisect import bisect_left, bisect_right

arr = [2, 5, 5, 8, 12, 16]

# Найти количество элементов x, таких что 5 <= x <= 12
L, R = 5, 12
left_idx = bisect_left(arr, L)    # Индекс первой пятерки: 1
right_idx = bisect_right(arr, R)  # Индекс первого числа > 12: 5

count = right_idx - left_idx
print(f"Количество элементов: {count}") # 4 (числа: 5, 5, 8, 12)

# Поиск по массиву кортежей с помощью аргумента key:
intervals = [(1, 3), (2, 6), (8, 10)]
idx = bisect_left(intervals, 2, key=lambda x: x[0]) # Ищет интервал с началом >= 2 (индекс 1)

---

# 6. itertools (Комбинаторика и префиксы)
Генераторы на Си. Работают на порядок быстрее, чем рекурсивный бэктрекинг.

Основные функции и сложность:

accumulate(arr, [func]) — префиксные суммы / максимумы / минимумы: O(N)
permutations(iterable, r=None) — перестановки длины r: O(\frac{N!}{(N-r)!})
combinations(iterable, r) — сочетания из N по r: O(\binom{N}{r})
product(*iterables, repeat=1) — декартово произведение (замена вложенных циклов): O(\prod |A_i|)
groupby(iterable, [key]) — группировка подряд идущих одинаковых элементов (RLE-сжатие): O(N)

Применение в CP: Префиксные суммы и RLE-сжатие

from itertools import accumulate, groupby, product
import operator

# 1. Префиксные суммы за O(N)
nums = [3, 1, 4, 1, 5]
pref = [0] + list(accumulate(nums)) # [0, 3, 4, 8, 9, 14]
# Сумма на отрезке [L, R] (1-индексация, с 2 по 4 элемент): pref[4] - pref[1] = 9 - 3 = 6

# Префиксные максимумы:
pref_max = list(accumulate(nums, max)) # [3, 3, 4, 4, 5]

# 2. Run-Length Encoding (RLE) строки "aaabbc" -> [('a', 3), ('b', 2), ('c', 1)]
s = "aaabbcaaa"
rle = [(char, len(list(group))) for char, group in groupby(s)]
print(rle) # [('a', 3), ('b', 2), ('c', 1), ('a', 3)]

# 3. Полный перебор битовых масок длины N (N <= 20)
n = 3
for mask in product([0, 1], repeat=n):
    # генерирует (0,0,0), (0,0,1), ..., (1,1,1)
    pass

---

# 7. math (Быстрая математика)
Все математические функции модуля реализованы на Си и исключают ошибки вещественной точности.

Основные функции:

math.gcd(*integers) — наибольший общий делитель: O(\log(\min(A, B)))
math.lcm(*integers) — наименьшее общее кратное
math.isqrt(n) — целочисленный квадратный корень \lfloor\sqrt{n}\rfloor (не падает от float overflow на числах 10^{18})
math.comb(n, k) — сочетания C_n^k (быстро считает огромные числа без факториалов)
math.perm(n, k) — число размещений P_n^k
math.factorial(n) — вычисляет точный факториал

import math

# НОД любого количества чисел
g = math.gcd(24, 36, 60) # 12

# Безопасный корень для огромных чисел
n = 10**18 + 7
root = math.isqrt(n)
print(root * root <= n) # True

# Подсчет числа способов выбрать 3 человек из 10
ways = math.comb(10, 3) # 120

---

# 8. sys (Шаблон быстрого ввода-вывода и стек)
Python-решения часто валятся с TLE или RE (Runtime Error) только из-за медленного input() или ограничения рекурсии.

Основной CP-бойлерплейт:

import sys

# 1. Быстрый построчный ввод вместо input()
input = sys.stdin.readline

# 2. Увеличение глубины рекурсии (по умолчанию 1000 - упадет на любом дереве)
sys.setrecursionlimit(300_000)

# 3. Для Python 3.11+: снятие ограничения на размер перевода огромных чисел в строку
sys.set_int_max_str_digits(100_000)

def main():
    # Быстрый вывод (быстрее print в циклах):
    # sys.stdout.write(f"{ans}\n")
    pass

# ЛАЙФХАК: Чтение ВСЕГО ввода сразу за O(1) чтение
# Полезно, если даны сотни тысяч чисел через пробел
def read_all():
    data = sys.stdin.read().split()
    if not data:
        return
    it = iter(data)
    n = int(next(it))
    m = int(next(it))
    # Дальше просто берем next(it)

if __name__ == '__main__':
    main()