Всем привет! Сегодня разбор задач с Codeforces, которые я решил: E1, G (1742), F, C (1739), C (1738), D1, G (1725), G (1722).
Ссылка на задачу: E1
Идея решения: Перебор x невозможен для полного диапазона y, но x ограничен a < x ≤ c, а y можно вычислять через gcd: x * y | a * b.
Алгоритм:
- Перебираем $$$x$$$ от $$$a+1$$$ до $$$c$$$.
- Вычисляем $$$g = \gcd(a \cdot b, x)$$$, чтобы выделить общий делитель.
- Вычисляем $$$y = \frac{a \cdot b}{g}$$$.
- Проверяем, попадает ли y в диапазон b < y ≤ d.
- Если есть подходящая пара — выводим x, y, иначе — -1, -1.
Особенности:
- Суть в том, что через gcd можно получить минимальное y, которое точно делит a*b вместе с x.
- Не требуется перебирать все пары (x, y), что экономит время.
Вывод: задача решается перебором x и прямым вычислением y через gcd.
Ссылка на задачу: G
Идея решения: Максимальный OR можно получить за первые log₂(max) операций, дальше добавление чисел не увеличивает результат.
Алгоритм:
- Заводим счетчик cnt = 0.
- Идем по массиву a[i] от 0 до min(log₂(1e9), n) и выбираем элемент, который добавляет максимальные новые биты к OR.
- Обновляем cnt на каждом шаге.
- Оставшиеся элементы добавляем в конец — они не изменяют результат OR.
Особенности:
- Ограничение по log₂(max) существенно упрощает перебор.
- Жадный выбор гарантирует, что на каждом шаге OR увеличивается максимально.
Вывод: жадная стратегия + добавление оставшихся элементов в конец обеспечивает оптимальный OR.
Ссылка на задачу: F
Идея решения: Сравниваем строки через частоты букв, чтобы не делать перебор всех символов для каждого запроса.
Алгоритм:
- Считаем частоты букв для каждой строки: cnt1 для строки a, cnt2 для b.
- Формируем s1 — отсортированные символы строки a с cnt1[i] > 0, s2 — обратная сортировка строки b с cnt2[i] > 0.
- Если s1 < s2 — ответ Да.
- Если s1 = s2, проверяем частоты: если для какого-то i cnt1[i] > cnt2[i] — ответ Нет.
- Если s1 > s2 — сразу Нет.
Особенности:
- Сортировка + обратная сортировка помогает учесть лексикографический порядок без прямого перебора.
- Проверка частот учитывает равные буквы, чтобы не ошибиться в случае совпадения строк.
Вывод: сравнение через сортировку и частоты обеспечивает быстрое решение для множества запросов.
Ссылка на задачу: C
Идея решения: Используем биномиальные коэффициенты и DP для подсчета выигрышей и проигрышей Алисы и Боба.
Алгоритм:
- Всего комбинаций: C(n, n/2).
- Считаем проигрыши Алисы dp[i] = C(i, i/2) — (C(i-1,(i/2-1)) + dp[i-1] + 1).
- Выигрыши Алисы: a = всего — b — c, где b = проигрыши, c = ничья (1).
- Учитываем, что первый ход Алисы важен: если её максимальная карта больше всех карт Боба — сразу выигрыш.
Особенности:
- DP позволяет учитывать предыдущие ходы и правильное распределение карт.
- Учитываем отдельный случай ничьи.
Вывод: через DP и биномиальные коэффициенты считаем все исходы игры.
Ссылка на задачу: C
Идея решения: Алиса выигрывает, если количество нечётных чисел позволяет ей получить чётную сумму.
Алгоритм:
- Считаем количество нечётных чисел mod 4.
- Если нечётных %4 == 0 → Алиса выигрывает.
- Если %4 == 1 → проверяем наличие чётных чисел для «защитного хода», чтобы забрать лишнее нечётное.
- Если %4 == 2 → Боб выигрывает сразу.
- Если %4 == 3 → Алиса гарантированно выигрывает, забирая два нечётных числа.
Особенности:
- «Защитный ход» — важная концепция: Алиса использует чётное число, чтобы оставить себе выигрышное нечётное.
- Разбор всех случаев %4 позволяет быстро определить победителя.
Вывод: стратегия зависит от остатка нечётных чисел по модулю 4 и возможности защитного хода.
Ссылка на задачу: D1
Идея решения: DP с map позволяет запоминать предыдущие значения и избегать повторного перебора.
Алгоритм:
- Инициализируем mp[x] = минимальное доступное значение для x.
- Если x уже встречался, продолжаем поиск от mp[x].
- Иначе находим первый свободный слот и обновляем mp[x].
- Так мы избегаем TLE для больших n.
Особенности:
- Map хранит минимальное число, с которого можно продолжать.
- Использование предыдущих значений ускоряет поиск свободных слотов.
Вывод: DP + map ускоряет поиск и позволяет обработать большие n.
Ссылка на задачу: G
Идея решения: Наблюдаем закономерность: последовательность блоков по 3 числа увеличивается на 4.
Алгоритм:
- Определяем первые три числа: ans1 = 3, ans2 = 5, ans3 = 7.
- Для n=4 корректируем ans1 → 4, чтобы сохранить правильную последовательность.
- Каждый блок по 3: ans_i += ((n+2)/3 — 1) * 4.
- Выводим ans в зависимости от n % 3.
Особенности:
- Разбивка на блоки помогает сразу рассчитать n-й элемент.
- Подстраиваем первые элементы для корректного результата на маленьких n.
Вывод: формула с блоками по 3 позволяет вычислить n-й элемент без полного перебора.
Ссылка на задачу: G
Идея решения: Создаем массив так, чтобы XOR всех элементов был 0 и не было дубликатов.
Алгоритм:
- До n-1: a[i] = i.
- Последний элемент: XOR всех предыдущих.
- Чтобы избежать дубликатов: можно до n-3 поставить a[i] = i, затем a[n-2] = 2^29, a[n-1] = 2^30, последний элемент = XOR всех предыдущих.
Особенности:
- Используем XOR для получения 0 в конце.
- Добавление больших чисел предотвращает дубликаты.
Вывод: формируем корректный массив с уникальными элементами и итоговым XOR = 0.
