Codeforces Round #340 (Div. 2) Editorial

Правка ru2, от komendart, 2016-01-24 11:57:00

617A - Слоник

Оптимально делать наибольший возможный шаг каждый раз. Поэтому слоник должен сделать сначала некоторое количество шагов на расстояние 5, а затем один или ноль шагов на меньшее расстояние. Следовательно, ответ равен .

Решение 15550796

617B - Шоколад

Нам дан массив, состоящий только из нулей и единиц. Мы должны разделить его на части, в каждой из которых ровно одна единица.

Особый случай: когда массив состоит только из нулей ответ равен нулю.

Рассмотрим общий случай. Во-первых нули на префиксе относятся к первому куску, нули на суффиксе относятся ко второму куску. Во-вторых, между каждой парой соседних единиц должно быть одно и только одно разделение частей. Между соседними единицами с индексами a < b всего b - a вариантов разделения. Поэтому мы должны перемножить эти значения для всех пар соседних единиц.

Бонус: каким является максимальный ответ при n ≤ 100?

Решение 15550806

617C - Поливка цветов

Первый радиус равен нулю или расстоянию от первого фонтана до какого-то цветка. Переберем все эти числа. Второй радиус будет равен максимальному из расстояний от второго фонтана до цветка, который не принадлежит кругу с первым радиусом. Теперь мы должны выбрать вариант с минимальным r12 + r22

Бонус: Я описал решение за O(n2). Можете ли вы решить задачу за O(nlogn)?

Решение за O(n2) 15550812

Решение за O(nlogn) 15550822

617D - Ломаная

Ответ равен одному, когда все координаты x или все координаты y совпадают.

Когда ответ равен двум? Переберем все пары точек. Пусть первая точка является началом ломаной, вторая концом ломаной. Только одна или две таких ломаных с двумя звеньями существуют. Они образуют прямоугольник с противоположными углами в первой и второй точке. Мы можем просто проверить принадлежность третьей точки прямоугольнику.

Иначе ответ всегда равен трем. Давайте построим вертикальные прямые через самую левую и через самую правую точки. Через третью точку построим горизонтальную прямую. Теперь, если мы удалим некоторые лишние лучи, получим подходящую ломаную.

Решение 15550843

617E - XOR и любимое число

У нас есть массив a

Давайте посчитаем массив (, ).

Xor подмассива равен .

Теперь запрос (l, r) заключается в подсчете количества пар i, j (l - 1 ≤ i < j ≤ r) .

Пусть мы знаем ответ на запрос (l, r) и знаем для всех v cnt[v] — количество вхождений v в .

Мы можем обновить за O(1) ответ и cnt если мы изменим правую или левую границу запроса на 1.

Поэтому мы можем решить задачу оффлайн за с помощью корневой эвристики (алгоритм Мо).

Решение 15550846

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru2 Русский komendart 2016-01-24 11:57:00 289
en5 Английский komendart 2016-01-24 11:51:18 363 Tiny change: 'wer for $n[Solution]$?\n\nSolu' - 100$?\n\nSolu'
ru1 Русский komendart 2016-01-24 11:38:19 3000 Первая редакция перевода на Русский
en4 Английский komendart 2016-01-23 21:17:57 274 Tiny change: 'XrpikpT)\n[Solutio' -
en3 Английский komendart 2016-01-23 21:00:09 23 Tiny change: ' expand it.\n\n[prob' - (published)
en2 Английский komendart 2016-01-23 20:56:47 230 Tiny change: 'uals to $\ceil{x/5}$' -
en1 Английский komendart 2016-01-23 20:41:01 2204 Initial revision (saved to drafts)