Олимпиадное программирование: с чего начать

Какие основы пригодятся

1. Начнём с полного перебора

n, s = map(int, input().split())
a = list(map(int, input().split()))
answer = 0
for i in range(n):
    for j in range(i + 1, n):
        if a[i] + a[j] == s:
            answer += 1
print(answer)

Второй индекс начинается с i + 1: число не складывается само с собой, а каждая пара рассматривается один раз. Проверок n(n − 1) / 2 — это O(n²). При n = 100 000 получится 4 999 950 000 проверок.

2. Вспомним числа, которые уже встречались

Для текущего x нужен партнёр S − x. В словаре храним, сколько раз каждое число встречалось до текущей позиции.

n, s = map(int, input().split())
a = list(map(int, input().split()))
seen = {}
answer = 0
for x in a:
    answer += seen.get(s - x, 0)
    seen[x] = seen.get(x, 0) + 1
print(answer)

Сначала считаем пары, потом добавляем x. Если поменять строки местами, при S = 6 число 3 ошибочно образует пару само с собой.

На каждой позиции учитываются ровно те подходящие партнёры, которые стоят раньше. Поэтому каждая пара будет посчитана один раз. В среднем решение выполняется за O(n) времени и использует O(n) дополнительной памяти; это оценка при обычной работе хеш-таблицы Python.

3. Проверим крайние случаи

Для уверенности можно сравнивать быстрый алгоритм с перебором на коротких случайных списках. Перебор становится удобным эталоном для проверки.

Что изучать дальше

1. Сортировка и частоты: как упорядочить данные и посчитать повторы.
2. Префиксные суммы: как быстро находить сумму на отрезке.
3. Два указателя и двоичный поиск: когда можно сократить перебор.
4. Графы и динамическое программирование: после уверенного освоения предыдущих приёмов.

Для конкретной олимпиады проверьте её правила: допустимые языки, ограничения времени и формат ввода. Эта задача учебная и не является официальным вариантом олимпиады.