Расскажите, пожалуйста, а что нужно было по условию сделать в задаче G и как ее решать?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
Название |
---|
Могу только рассказать, что надо было сделать, решать не умею:(
Дано не более 20 чисел (каждое не более 100) и число k (не более 6). Также дано число L.
Мы умеем выбирать любое упорядоченное подмножество наших чисел размером не более k (упорядоченное в плане индексов). Из этого подмножества мы можем брать любой (возможно, закругленный) подотрезок. Число считается достижимым для заданного упорядоченного подмножества, если мы можем получить его как xor какого-то из таких отрезков.
Ответом для подмножества назовем такое наибольшее число R, что для него достижимы все числа от L до R. (либо -1 если L недостижимо). Наша задача — сказать максимальный ответ по всем подмножествам.
Ну и еще гарантируется, что тесты генерировались рандомно
Пробовал упихать отжиг — не удалось.
У кого-то есть размороженная таблица, кстати?
UPD И еще — расскажите как решать E и F?
Задача: найдите такой упорядоченный поднабор данных чисел размера k, что как можно больше чисел начиная с L представимы в виде ксора какого-то подотрезка (закольцованного).
Я пихал такое решение:
1) Перебираем kn упорядоченных выборов. Для удобства массив сортируем и отсекаем ситуации, когда первый элемент выборки не минимальный, также отсекаемся, если от разворота последовательность станет меньше.
2) Теперь мы хотим получить все числа, которые можно получить из данной шестерки. Я считал только числа, которые можно получить на подотрезках длины не больше 3, возвращал маской в int128. Делается прекалком — посчитать ксоры, которые можно получить из трех элементов и всевозможные ксоры на префиксах и суффиксах. Потом из двух частей собираем то, что можно получить из шестерки — это буквально 4 дополнительных варианта.
3) Теперь проверяем для всех чисел начиная с L, можно ли представить x или ксор нашей шестерки без x. Тесты случайные, в среднем довольно быстро отсечемся (можно локально погенерировать).
Аккуратно написанное это вроде без каких-либо еще оптимизаций заходит.
Позвольте такую глупость спросить: как решать A?
У меня было так.
1) Все X-ы должны быть последними, потому что они не добавляют урона или времени, и влияние Y-ов и Z-ов таким образом будет максимально.
2) Дальше динамика. dp[i][j] — какой максимальный урон получится на префиксе [1, i], если там ровно j Y-ов, ровно i — j Z-ов. При этом считается, что в оставшемся суффиксе будут только X-ы. Но урон от X-ов в этой динамике не хранится, для того чтобы можно было ее пересчитывать. Дальше в пересчете либо на i-ом месте ставишь Y, либо Z. Тогда ответ либо когда ты везде ставишь X-ы. Либо максимум по всем dp[i][j] + соответствующий урон от суффикса с X-ами. Получается O(N^2).
Что-то подробнее надо?
Опередили :)
Понятно, что первый тип башен может всегда идти последними.
Тогда весь вопрос в том, как расположить башни второго и третьего типа на префиксе.
Давай напишем динамику d[i][j] = максимальный урон, если мы разместили уже i башен второго типа и j третьего.
Переходы очень простые, так как по этим количествам мы можем высчитать время на проход и урон в секунду.
После того как посчитали, просто для каждой пары из динамики попробуем добавить на остаток башни первого типа и обновить ответ.
Заметим, что башни, которы бьют по x можно ставить в конец. Действительно, ставить их раньше башни, которая бьет по y нет смысла (иначе башня которая бьет по y будет бить меньше времени). Аналогично, не имеет смысла ставить их раньше башни, которая замедляет.
Теперь пишем динамику по тому, сколько башен-замедлялок и башен, которые бьют по y мы уже поставили на префиксе. Переходы — до конца ставим башни, которые бьют по х, или ставим замедлялку, или ставим башню, которая бьет по y.
UPD Super slow :(
Спасибо!
Ни у кого нет условий задач и таблицы после разморозки?
Ссылка на условия: https://www.sendspace.com/file/0zga3f
Ссылка на сам контест: http://opentrains.mipt.ru/~ejudge/team.cgi?contest_id=000800
Кто-то знает или будет дорешивание (может можно добавить в codeforces gym)?
Как решать задачу про приятное множество точек на плоскости? (не помню какой у нее номер)