Time Limit Exceeded: почему решение не проходит по времени и как его ускорить

Программа проходит пример из условия, выдаёт правильные ответы, а проверяющая система пишет: Time Limit Exceeded, «превышено ограничение по времени». Сокращённо — TLE. Это значит, что на каком-то тесте программа работала дольше, чем разрешено, и её остановили.

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

Все замеры в статье сделаны на одном компьютере компилятором g++ 14.2 с флагом -O2. На другой машине цифры будут иными, а соотношения — такими же.

Сколько операций успевает компьютер

Удобный ориентир: за секунду программа на C++ выполняет порядка ста миллионов простых действий — сложений, сравнений, обращений к массиву. Число грубое, но для оценки его хватает.

Отсюда способ проверить решение ещё до того, как Вы его написали. Возьмите самое большое N из ограничений, подставьте в формулу числа операций и сравните с 10^8.

Если в условии N до 200 000, а в решении два вложенных цикла, это 4 · 10^10 действий. Ждать бесполезно: нужен другой алгоритм.

Причина 1. Алгоритм слишком медленный

Самая частая. Задача: посчитать, сколько различных чисел среди N заданных, N до 200 000.

Решение «в лоб» для каждого числа проверяет, не встречалось ли оно раньше:

int distinct = 0;
for (int i = 0; i < n; ++i) {
    bool seen = false;
    for (int j = 0; j < i; ++j) {
        if (a[j] == a[i]) {
            seen = true;
            break;
        }
    }
    if (!seen) ++distinct;
}

На 200 000 случайных чисел оно работало 4,6 секунды. А так — 0,04 секунды, в сто с лишним раз быстрее:

std::sort(a.begin(), a.end());
int distinct = std::unique(a.begin(), a.end()) - a.begin();

После сортировки одинаковые числа стоят рядом, и хватает одного прохода. Первое решение делает порядка N^2 действий, второе — порядка N log N.

Никакая «оптимизация» первого варианта не поможет: ускорить его вдвое можно, в сто раз — нет. Если оценка по таблице не сходится, меняйте идею, а не детали.

Причина 2. Медленный ввод и вывод

Задача: прочитать миллион чисел и после каждого вывести текущую сумму. Привычный код:

for (int i = 0; i < n; ++i) {
    int x;
    std::cin >> x;
    sum += x;
    std::cout << sum << std::endl;
}

работал 0,34 секунды. Тот же код с двумя изменениями — 0,03 секунды:

std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

for (int i = 0; i < n; ++i) {
    int x;
    std::cin >> x;
    sum += x;
    std::cout << sum << '\n';
}

Что изменилось:

• sync_with_stdio(false) отключает синхронизацию потоков C++ с функциями scanf и printf. После этого смешивать их в одной программе нельзя.
• cin.tie(nullptr) отменяет сброс вывода перед каждым чтением.
• '\n' вместо std::endl. Манипулятор endl не только переводит строку, но и каждый раз отправляет накопленный вывод наружу. Миллион строк — миллион таких отправок.

Десятикратная разница сама по себе решение не спасёт, но при больших объёмах данных часто отделяет «прошло» от TLE. Первые две строки стоит писать в начале main в каждой задаче, где ввод большой.

Причина 3. Лишние копии

Вектор, переданный в функцию по значению, копируется целиком при каждом вызове:

long long get(std::vector<int> values, int index) {   // копия
    return values[index];
}

Сто тысяч вызовов такой функции с вектором из ста тысяч чисел заняли 0,72 секунды, хотя полезной работы в ней — одно обращение к элементу. С передачей по ссылке время не удалось измерить, настолько оно мало:

long long get(const std::vector<int>& values, int index) {   // ссылка
    return values[index];
}

То же относится к строкам. Большие объекты, которые функция только читает, передавайте как const T&.

Близкая ловушка — сборка строки сложением: s = s + c в цикле каждый раз создаёт новую строку и копирует в неё старую. Пишите s += c.

Причина 4. Рекурсия, которая считает одно и то же

long long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

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

Каждые пять шагов время растёт примерно в одиннадцать раз. Цикл считает то же самое мгновенно:

long long previous = 0, current = 1;
for (int i = 0; i < n; ++i) {
    long long next = previous + current;
    previous = current;
    current = next;
}

Если рекурсия нужна, запоминайте уже посчитанные значения в массиве. Этот приём называется мемоизацией.

Причина 5. Цикл, который не заканчивается

Иногда TLE означает не «медленно», а «бесконечно». Классический пример — обратный проход с беззнаковым счётчиком:

for (std::size_t i = a.size() - 1; i >= 0; --i) {
    // ...
}

Тип size_t не бывает отрицательным. После нуля счётчик становится огромным числом — 18446744073709551615, и условие i >= 0 истинно всегда. Компилятор с флагом -Wall -Wextra об этом предупреждает:

warning: comparison of unsigned expression in '>= 0' is always true

Другие источники бесконечных циклов: забытое изменение счётчика в while, условие != там, где шаг перепрыгивает нужное значение, чтение ввода без проверки, что он закончился.

Причина 6. Лишняя работа внутри цикла

• Вызов strlen(s) в условии цикла пересчитывает длину строки на каждом шаге. Сохраните длину в переменную.
• v.erase(v.begin()) сдвигает все элементы вектора. Удалять из начала в цикле — это N^2. Используйте std::deque или индекс «головы».
• Поиск в std::vector через std::find внутри цикла — снова N^2. Нужна проверка «есть ли» — возьмите std::set или std::unordered_set.
• pow(x, 2) для целых чисел медленнее и опаснее, чем x * x.

Как найти медленное место

1. Оцените сложность. Подставьте наибольшее N в число операций. Если получилось больше 10^8–10^9, дело в алгоритме, и замеры не нужны.
2. Сделайте большой тест. Маленький пример из условия ничего не покажет. Сгенерируйте вход наибольшего размера — случайный и «плохой»: все числа одинаковые, уже отсортированный массив, одни максимальные значения.
3. Соберите с оптимизацией. Без флага -O2 программа может работать в несколько раз медленнее. Проверяющие системы обычно его включают.
4. Измерьте время на большом тесте.
5. Проверьте, что цикл вообще заканчивается. Если программа «висит» и на маленьком тесте — это бесконечный цикл, а не медленный алгоритм.

Команды для сборки и замера в Linux и macOS:

g++ -O2 -std=c++26 main.cpp -o main
time ./main < big.txt > /dev/null

Порядок действий при TLE

1. Найдите в условии наибольшие ограничения.
2. Оцените число операций своего решения.
3. Не сходится — ищите алгоритм быстрее: сортировка, двоичный поиск, префиксные суммы, словарь вместо перебора.
4. Сходится — проверьте ввод-вывод, передачу по значению и лишнюю работу в циклах.
5. Измерьте время на самом большом тесте, прежде чем отправлять снова.

TLE — не единственный вердикт, с которым сталкиваются на первых задачах. Если программа падает, поможет статья «Segmentation fault в C++: что это за ошибка и как найти причину», а если выдаёт странные числа — «Мусор в переменных и неопределённое поведение в C++». Потренироваться можно на подборке «Задачи по C++ для начинающих с решениями».