[problem:1106A]↵
------------------↵
↵
Автор контеста случайно опубликовал разбор задачи в её условии. Необходимо перебрать клетку и проверить, что она является центром креста.↵
↵
Асимптотика $O(n * m)$↵
↵
Код:[submission:49284766]↵
↵
[problem:1106B]↵
------------------↵
↵
Заметим, что каждый человек получит либо $d_{j}$ блюд типа $t_{j}$, либо $r_{t_{j}}$ блюд типа $t_{j}$ и получит целиком и получит некоторый префикс самых дешевых блюд и, возможно, часть запасов какого-либо блюда. Будем поддерживать set доступных блюд, отсортированный по стоимости. На каждой итерации, кроме блюд, которые исчезли навсегда, мы просматриваем не более одного блюда.↵
↵
Асимптотика $O((n + m)\log{}n)$↵
↵
Код:[submission:49285005]↵
↵
[problem:1106C]↵
------------------↵
↵
Для начала заметим, что в каждой группе должно быть ровно два элемента, так как $(a + b) ^ 2 > a ^ 2 + b ^ 2$ для положительных $a$ и $b$↵
↵
Покажем, что $a_{i}$ и $b_{i}$ должны стоять на "противоположных" позициях в отсортированном массиве, так как↵
↵
$\sum_{i = 1}^{n / 2} (a_{i} + b_{j})^2 = \sum_{i = 1}^{n / 2} a_{i}^2 + \sum_{i = 1}^{n / 2} b_{j}^2 + \sum_{i = 1}^{n / 2}\sum_{j = 1} ^ {n / 2} a_{i} * b_{j}$↵
↵
То есть нам надо минимизировать третье слагаемое. Теперь такой выбор $a_{i}$ и $b_{i}$ следует из транснеравенства ([доказательтво](https://www.mccme.ru/s43/math/uroki/2009_2010/9mat_0910/spec/55_nerav3_lect.pdf)).↵
↵
Асимптотика $O(n\log{}n)$↵
↵
Код:[submission:49285168]↵
↵
[problem:1106D]↵
------------------↵
↵
Допустим, мы знаем префикс ответа длины $i$. Тогда на следующем шаге мы можем пойти в любую вершину, соседнюю с уже посещенной. Очевидно, что стоит идти в вершину с минимальным номером. ↵
↵
Это можно сделать используя bfs с приоритетной очередью.↵
↵
Асимптотика $O(n\log{}n + m)$↵
↵
Код:[submission:49285447]↵
↵
↵
[problem:1106E]↵
------------------↵
↵
Задача решается методом динамического программирования. Обозначим за $dp[i][j]$ минимальное количество монет у Боба, если он сейчас выбирает конверт в момент времени $i$ и Алиса уже отвлекла его $j$ раз.↵
↵
Тогда из $dp[i][j]$ можно перейти в $dp[i + 1][j + 1]$ (если Алиса отвлекает его на $i$-том ходе) и в $dp[d_choice + 1][j]$, где $d_{choice}$ — $d$ конверта, который выберет Боб.↵
↵
Если использовать метод сканирующей прямой, то можно в каждой момент поддерживать set доступных конвертов отсортированный по убыванию $w$. Тогда мы сможем узнавать выбор Боба на каждой итерации за $O(\log{}n)$.↵
↵
Асимптотика $O(n\log{}k + n * m)$↵
↵
Код:[submission:49285694]↵
↵
[problem:1106F]↵
------------------↵
↵
В разработке.
------------------↵
↵
Автор контеста случайно опубликовал разбор задачи в её условии. Необходимо перебрать клетку и проверить, что она является центром креста.↵
↵
Асимптотика $O(n * m)$↵
↵
Код:[submission:49284766]↵
↵
[problem:1106B]↵
------------------↵
↵
Заметим, что каждый человек получит либо $d_{j}$ блюд типа $t_{j}$, либо $r_{t_{j}}$ блюд типа $t_{j}$ и получит целиком и получит некоторый префикс самых дешевых блюд и, возможно, часть запасов какого-либо блюда. Будем поддерживать set доступных блюд, отсортированный по стоимости. На каждой итерации, кроме блюд, которые исчезли навсегда, мы просматриваем не более одного блюда.↵
↵
Асимптотика $O((n + m)\log{}n)$↵
↵
Код:[submission:49285005]↵
↵
[problem:1106C]↵
------------------↵
↵
Для начала заметим, что в каждой группе должно быть ровно два элемента, так как $(a + b) ^ 2 > a ^ 2 + b ^ 2$ для положительных $a$ и $b$↵
↵
Покажем, что $a_{i}$ и $b_{i}$ должны стоять на "противоположных" позициях в отсортированном массиве, так как↵
↵
$\sum_{i = 1}^{n / 2} (a_{i} + b_{j})^2 = \sum_{i = 1}^{n / 2} a_{i}^2 + \sum_{i = 1}^{n / 2} b_{j}^2 + \sum_{i = 1}^{n / 2}\sum_{j = 1} ^ {n / 2} a_{i} * b_{j}$↵
↵
То есть нам надо минимизировать третье слагаемое. Теперь такой выбор $a_{i}$ и $b_{i}$ следует из транснеравенства ([доказательтво](https://www.mccme.ru/s43/math/uroki/2009_2010/9mat_0910/spec/55_nerav3_lect.pdf)).↵
↵
Асимптотика $O(n\log{}n)$↵
↵
Код:[submission:49285168]↵
↵
[problem:1106D]↵
------------------↵
↵
Допустим, мы знаем префикс ответа длины $i$. Тогда на следующем шаге мы можем пойти в любую вершину, соседнюю с уже посещенной. Очевидно, что стоит идти в вершину с минимальным номером. ↵
↵
Это можно сделать используя bfs с приоритетной очередью.↵
↵
Асимптотика $O(n\log{}n + m)$↵
↵
Код:[submission:49285447]↵
↵
↵
[problem:1106E]↵
------------------↵
↵
Задача решается методом динамического программирования. Обозначим за $dp[i][j]$ минимальное количество монет у Боба, если он сейчас выбирает конверт в момент времени $i$ и Алиса уже отвлекла его $j$ раз.↵
↵
Тогда из $dp[i][j]$ можно перейти в $dp[i + 1][j + 1]$ (если Алиса отвлекает его на $i$-том ходе) и в $dp[d_choice + 1][j]$, где $d_{choice}$ — $d$ конверта, который выберет Боб.↵
↵
Если использовать метод сканирующей прямой, то можно в каждой момент поддерживать set доступных конвертов отсортированный по убыванию $w$. Тогда мы сможем узнавать выбор Боба на каждой итерации за $O(\log{}n)$.↵
↵
Асимптотика $O(n\log{}k + n * m)$↵
↵
Код:[submission:49285694]↵
↵
[problem:1106F]↵
------------------↵
↵
В разработке.
