Блог пользователя CleRIC

Автор CleRIC, 10 лет назад, По-русски

385A - Медведь и малина

В этой задаче нужно было понять, что ответ это максимум из a[i] - a[i - 1] - c, для i = 2..n и не забыть, что ответ не может быть отрицательным, так как медведь может не занимать в долг бочонок меда.

385B - Медведь и строки

В этой задаче нужно было написать решение оптимальней наивного. Для этого, например, можно перебирать первым циклом левый индекс l рассматриваемой подстроки, а вторым циклом правый индекс r рассматриваемой подстроки (l ≤ r). Если на какой-то позиции i нашлась подстрока "bear", значит все подстроки x(l, j) (i ≤ j), также содержат "bear" в качестве подстроки. Значит к ответу можно сразу прибавить |s| - j + 1 и выйти из второго цикла. Также требовалось понять, что если в строке x(l, j) не было подстроки "bear", тогда в строке x(l, j + 1) подстрока "bear" могла появиться только в последних четырех символах.

385C - Медведь и простые числа

В этой задаче нужно было решить несколько подзадач:

1) Посчитать количество вхождений каждого числа от 2 до 107 в данный в задаче набор чисел. Это можно делать быстро так. Завести массив count на 107 элементов и при считывании чисел прибавлять count[x]++.

2) Теперь научимся считать f(x).

Для начала нужно найти все простые числа до 107 и посчитать для каждого простого числа — f(x).

Как посчитать f(2)? Нужно сложить count[2],count[4],count[6],count[8],...

Как посчитать f(5)? Нужно сложить count[5],count[10],count[15],count[20],...

Как посчитать f(x)? Нужно сложить count[x],count[2·x],count[3·x],count[4·x],...

Можно заметить похожесть на алгоритм решета Эратосфена http://e-maxx.ru/algo/eratosthenes_sieve и немного видоизменить его. Также будем сохранять в массиве pre результаты этих вычислений. А именно pre[x] = f(x).

3) Теперь можно посчитать префиксные суммы на массиве pre. Это делается одним проходом слева направо, прибавляя pre[i - 1] к pre[i].

4) Зная префиксные суммы, можно отвечать за O(1) на запрос [l, r]. Это делается так pre[r] - pre[l - 1].

5) Теперь можно считывать запросы и сразу отвечать на них. При этом не стоит забывать, что правая граница в запросе может быть до 2·109, поэтому правую границу можно всегда уменьшать до 107, так как бОльших чисел в изначальном массиве все равно нет.

385D - Медведь и прожекторы

В этой задаче нужно было понять, что если дорога уже освещена расстоянием в dist, то следующим прожектором оптимально освещать так, чтобы левая точка освещения на оси X была равна l + dist.

Предположим, что сейчас дорога освещена с l до d. Как теперь найти самую правую точку на оси X, которая будет освещена следующим прожектором?

Для этого достаточно использовать понятие вектора и матрицы поворота.

Находим вектор (dx, dy) от прожектора до точки (d, 0). (dx, dy) = (d - x, 0 - y).

Далее этот вектор нужно повернуть на angle градусов. Для этого можно использовать матрицу поворота.

(dx, dy) = (dx·cos(angle) - dy·sin(angle), dx·sin(angle) + dy·cos(angle))

Далее этот вектор нужно домножить на k таким образом, чтобы dy стал равен единице.

Ну и теперь можно определить самую правую освещенную точку на оси X. Она равна x - y·dx.

Также не стоит забывать, что правая точка может находится где-то в бесконечности.

На этом геометрия в этой задаче закончилась.

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

Для этого стоит применить подход динамического программирования. А именно, хранить ответ для масок прожекторов.

dp[i] = оптимальный ответ для такой-то маски i. Обычно под масками подразумевают целое число, в строковой бинарной записи числа которого, стоят 0 и 1. Допустим на 2 позиции стоит 1 — это означает, что 2 прожектор уже был использован. Например, dp[6] — (61102) оптимальный ответ, если уже использованы 2 и 3 прожектора.

Идея теперь такая. Перебираем маски в динамике dp[i]. Перебираем в i маске неиспользованные прожекторы j и обновляем ответ для маски, где этот прожектор уже используется — dp[ i or 2j ] = max( dp[ i or 2j ], dp[ i ] + вычисление_самой_правой_точки()). Так как мы уже знаем как находить самую правую освещенную точку, то обновление ответа для новой маски не составит труда.

385E - Медведь в поле

В этой задаче можно было заметить несколько вещей:

1) Заметить, что решение моделированием не проходит по времени, так как t  ≤  1018.

2) Далее можно убедиться, что задачу не решить отдельно по x и отдельно по y, так как x и y зависят друг от друга при вычислениях.

3) Также не проходит достаточно стандартный метод с поиском цикла (то есть мы попадаем в тоже самое состояние через некоторый небольшой промежуток времени). Такого может не произойти долгое время, так как ограничения на координаты большие.

Как тогда решать.

Пусть у нас есть матрица (xi, yi, dxi, dyi, ti, 1).

Умножив ее на такую матрицу long long base[6][6] = {

{2,1,1,1,0,0},

{1,2,1,1,0,0},

{1,0,1,0,0,0},

{0,1,0,1,0,0},

{0,0,1,1,1,0},

{0,0,2,2,1,1} };

мы получим значения на следующем шаге.

Откуда взялась эта матрица? Давайте распишем как меняются параметры с каждым шагом и увидим похожесть на матрицу.

x = x + y + dx + dy + t + 0·1.

y = x + y + dx + dy + t + 0·1.

dx = x + y + dx + dy + t + 2·1.

dy = x + y + dx + dy + t + 2·1.

t = x + y + dx + dy + t + 1·1.

1 = x + y + dx + dy + t + 1·1.

Таким образом, возведя матрицу base в степень t - 1, и потом умножив матрицу (sx, sy, dx, dy, t, 1) на base, получим значения в момент времени t.

Матрицу можно возводить в степень быстро по принципу быстрого возведения в степень по модулю. http://e-maxx.ru/algo/binary_pow

Перемножаются матрицы за куб. Итоговое количество операций 63·log(t)

Полный текст и комментарии »

Разбор задач Codeforces Round 226 (Div. 2)
  • Проголосовать: нравится
  • +85
  • Проголосовать: не нравится

Автор CleRIC, 10 лет назад, По-русски

Всем привет!

Скоро, 24 января в 19:30 MSK, состоится очередной Codeforces Round #226 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.

Задачи были подготовленны группой авторов в составе — Алексей Чесноков (CleRIC), Кирилл Бутин (KirillB) и Иван Попович (NVAL). Это наш первый раунд на Codeforces и мы надеемся, что все пройдет хорошо.

Вам предстоит помочь герою задач — обычному медведю.

Благодарим Gerald, Delinur, Aksenov239 за помощь в подготовке соревнования и MikeMirzayanov за систему.

Разбалловка стандартная: 500-1000-1500-2000-2500.

Удачи!

UPD: Раунд перенесен на 5 минут позже.

UPD: Разбор задач

UPD: Надеемся, что раунд вам понравился.

Поздравляем победителей:

  1. cptbtptp

  2. SquirrelDetected

  3. MahooshojoNHB

  4. Dong5k

  5. yada

Полный текст и комментарии »

  • Проголосовать: нравится
  • +180
  • Проголосовать: не нравится