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 до 10⁷ в данный в задаче набор чисел. Это можно делать быстро так. Завести массив count на 10⁷ элементов и при считывании чисел прибавлять count[x]++.

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

Для начала нужно найти все простые числа до 10⁷ и посчитать для каждого простого числа — 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·10⁹, поэтому правую границу можно всегда уменьшать до 10⁷, так как бОльших чисел в изначальном массиве все равно нет.

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] — (6 — 110₂) оптимальный ответ, если уже использованы 2 и 3 прожектора.

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

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

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

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

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

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

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

Пусть у нас есть матрица (x_i, y_i, dx_i, dy_i, t_i, 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 = 2·x + 1·y + 1·dx + 0·dy + 0·t + 0·1.

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

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

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

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

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

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

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

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