Алгоритми для змагального програмування

Український переклад cp-algorithms.com — однієї з найповніших збірок алгоритмів для змагального програмування.

• 162 статті — від бінарного піднесення до степеня до суфіксних автоматів і потоків
• 4 мови прикладів — кожен фрагмент коду доступний на C++, Python, TypeScript і Go
• Перевірений код — усі приклади запускалися й звірялися з оригінальною реалізацією

Обери свою мову

Перемкни вкладку нижче — вибір збережеться і застосується до всіх статей сайту:

C++

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

Python

def binpow(a: int, b: int) -> int:
    res = 1
    while b > 0:
        if b & 1:
            res *= a
        a *= a
        b >>= 1
    return res

TypeScript

function binpow(a: bigint, b: bigint): bigint {
  let res = 1n;
  while (b > 0n) {
    if (b & 1n) res *= a;
    a *= a;
    b >>= 1n;
  }
  return res;
}

Go

func binpow(a, b int64) int64 {
	var res int64 = 1
	for b > 0 {
		if b&1 == 1 {
			res *= a
		}
		a *= a
		b >>= 1
	}
	return res
}

Розділи

Розділ	Що всередині
Алгебра	Бінарне піднесення до степеня, решето Ератосфена, модульна арифметика, FFT, довга арифметика
Структури даних	Дерево Фенвіка, дерево відрізків, СНМ, розріджена таблиця, декартове дерево
Динамічне програмування	Вступ до ДП, рюкзак, НЗП, оптимізації Кнута та «розділяй і володарюй»
Графи	BFS, DFS, Дейкстра, MST, LCA, мости й точки зчленування, потоки, парування
Обробка рядків	Хешування, префікс-функція, Z-функція, суфіксні масив/автомат/дерево, Ахо-Корасік
Комбінаторика	Біноміальні коефіцієнти, числа Каталана, включення-виключення, лема Бернсайда
Геометрія	Базові операції з векторами, опукла оболонка, перетини, замітаюча пряма, Делоне
Лінійна алгебра	Метод Гауса, ранг матриці, визначник
Чисельні методи	Бінарний і тернарний пошук, метод Ньютона, інтегрування
Інше	Теорія ігор, задача Йосипа, розклади, послідовності

Повний перелік — у бічній панелі «Статті», а добірка найуживаніших інструментів з підказками «коли що брати» — на сторінці Найпопулярніші алгоритми.

З чого почати

Якщо ти новачок у змагальному програмуванні, радимо такий маршрут:

1. Бінарне піднесення до степеня — класичний перший алгоритм
2. Алгоритм Евкліда — НСД за $O(\log n)$
3. Решето Ератосфена — усі прості до $n$
4. Бінарний пошук — фундамент половини задач
5. BFS і DFS — обходи графів
6. Вступ до динамічного програмування
7. Дерево Фенвіка — перша «серйозна» структура даних

Про проєкт

Це неофіційний переклад cp-algorithms.com. Оригінальні статті поширюються за ліцензією CC BY-SA 4.0; переклад зберігає структуру, формули та C++-код оригіналу, додаючи українську термінологію і приклади на Python, TypeScript та Go.

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