Неофициальный разбор Codeforces Round #536 (Div. 2)

Revision ru4, by _overrated_, 2019-01-31 20:42:29

1106A - Lunar New Year and Cross Counting

Автор контеста случайно опубликовал разбор задачи в её условии. Необходимо перебрать клетку и проверить, что она является центром креста.

Асимптотика O(n * m)

Код:49284766

1106B - Lunar New Year and Food Ordering

Заметим, что каждый человек получит либо dj блюд типа tj, либо rtj блюд типа tj и получит целиком и получит некоторый префикс самых дешевых блюд и, возможно, часть запасов какого-либо блюда. Будем поддерживать set доступных блюд, отсортированный по стоимости. На каждой итерации, кроме блюд, которые исчезли навсегда, мы просматриваем не более одного блюда.

Асимптотика

Код:49285005

1106C - Lunar New Year and Number Division

Для начала заметим, что в каждой группе должно быть ровно два элемента, так как (a + b)2 > a2 + b2 для положительных a и b

Покажем, что ai и bi должны стоять на "противоположных" позициях в отсортированном массиве, так как

То есть нам надо минимизировать третье слагаемое. Теперь такой выбор ai и bi следует из транснеравенства (доказательтво).

Асимптотика

Код:49285168

1106D - Lunar New Year and a Wander

Допустим, мы знаем префикс ответа длины i. Тогда на следующем шаге мы можем пойти в любую вершину, соседнюю с уже посещенной. Очевидно, что стоит идти в вершину с минимальным номером.

Это можно сделать используя bfs с приоритетной очередью.

Асимптотика

Код:49285447

1106E - Lunar New Year and Red Envelopes

Задача решается методом динамического программирования. Обозначим за dp[i][j] минимальное количество монет у Боба, если он сейчас выбирает конверт в момент времени i и Алиса уже отвлекла его j раз.

Тогда из dp[i][j] можно перейти в dp[i + 1][j + 1] (если Алиса отвлекает его на i-том ходе) и в dp[dchoice + 1][j], где dchoice — d конверта, который выберет Боб.

Если использовать метод сканирующей прямой, то можно в каждой момент поддерживать set доступных конвертов отсортированный по убыванию w. Тогда мы сможем узнавать выбор Боба на каждой итерации за .

Асимптотика

Код:49285694

1106F - Lunar New Year and a Recursive Sequence

В разработке.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru8 Russian _overrated_ 2019-02-01 16:40:35 692 (опубликовано)
ru7 Russian _overrated_ 2019-02-01 16:28:21 1873 Мелкая правка: '------\n\nКод:[s' -> '------\n\nДопустим $f_{k} == x$\n\nКод:[s' (сохранено в черновиках)
ru6 Russian _overrated_ 2019-02-01 15:28:16 38 Мелкая правка: '------\n\nВ разработке.' -> '------\n\nКод:[submission:49321335]\n'
ru5 Russian _overrated_ 2019-01-31 20:45:18 4 Мелкая правка: 'тика $O(n * m)$\n\nКод:' -> 'тика $O(n ^ 2)$\n\nКод:'
ru4 Russian _overrated_ 2019-01-31 20:42:29 147
ru3 Russian _overrated_ 2019-01-31 20:23:48 24 (опубликовано)
ru2 Russian _overrated_ 2019-01-31 20:19:47 791 Мелкая правка: 'й очередью' -> 'й очередью.\n\nАсимптотика $O(n\log{}n)$\n\n\n'
ru1 Russian _overrated_ 2019-01-31 20:03:30 1701 Первая редакция (сохранено в черновиках)