Менее суток осталось до раунда 2B, не забывайте! Начало в 20:00 MSK в субботу.
50 человек проходит в раунд 3.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | jiangly | 3670 |
| 3 | Kevin114514 | 3657 |
| 4 | maroonrk | 3355 |
| 5 | Um_nik | 3353 |
| 6 | squareOf105 | 3346 |
| 7 | tourist | 3343 |
| 8 | strapple | 3324 |
| 9 | heuristica | 3322 |
| 10 | jiangbowen | 3291 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 143 |
| 5 | Um_nik | 141 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 134 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
Стоит напомнить, что те, кто уже прошел, имеют право поучаствовать в TCO 2B Parallel Round
50 человек? Это забавно) Уже бы всем разрешили.
не знал:)
а те, кто не прошел во второй раунд, могут писать вне конкурса?
PS. Понятно, нет
Почему в Medium не работает решение "переберем подотрезок первого хода, а дальше промоделируем жадно"?
а почему это именно подотрезок?
Ясно, спасибо. Несложно доказать, что подотрезок (на отсортированном массиве, конечно) выбирается при b.size() == 2. Показалось, что на в общем случае это тоже верно.
А жадное моделирование после выбора подмножества ведь уже работает? UPD: работает, уже снизу ответили.
Потому что выбранные книги не обязательно подотрезок, например при
books = { 1, 5, 6 }
moves = { 2, 2, 1 }
нужно выбирать { 1, 6 }
А если выбирать всегда часть самых маленьких и часть самых больших, тоже не будет работать?
Тот же семпл.
Ну как же, тут мы попробуем все три множества: { 1, 5 } { 1, 6 } { 5, 6 } Т.е. перебираем сколько книг возьмем с начала, остальные берем с конца. Идея как бы в том что мы хотим сколько-то очень тяжелых для соперника и сколько-то максимально легких для себя.
Наврал, другой тест:
Пусть мы должны получить большую книгу из 2х. Тогда надо выбрать с минимально разницей
books={1, 100,101,1000} moves={2,1}Да, на этом тесте не работает. Спасибо за объяснение.
Он не обязательно подотрезок Например, пусть moves = {4, 3, 1}, а books = {10, 9, 3, 2, 1}. Тогда надо брать 10, 3, 2, 1, так как нам достанется две средние книги
А с чего бы первым ходом должен быть подотрезок?
Как решать 550?
Перекладывать надо всегда самые тяжелые. Таким образом, по набору ходов можно понять, у кого будет самая тяжелая книга, у кого вторая по тяжести итд. Дальше, зная это, сортируем книжки и делаем ДП от двух параметров -- текущая книга, сколько книг взято.
Заметим, что кроме первого хода выгодно скидывать большие книги.
Занумеруем книги, взятые после первого хода, посмотрим, что кому попадет.
Далее динамика за первого игрока:
[сколько книг посмотрели(из всех)][сколько выбрали]
ну и ответ будет в dp[books.size()][moves[0]]
Понятно, что начиная со второго хода выгодно передавать самые тяжелые книги. Таким образом можно посчитать, кому какая по порядку среди выбранных книга достанется. Остается запустить двумерную динамику, в которой состояние (мы взяли k из m самых тяжелых книг) -> (самая большая разница, самая большая сумма при такой разнице)
Расскажите, пожалуйста, тысячу.
Ну, понятно, что у каждого числа первая цифра — 1, так что надо найти в каждом числе сколько раз сменились разряды + сколько с нулями на конце (ну и понятно, что для последнего числа не надо его 0 на конце считать) На самом деле надо посчитать числа вида
, сколько среди них 1 и 2, ну и вычесть n, так как лидирующий 01 мы тоже посчитаем. Заметим, что yij для фиксированного j периодично с периодом 2j + 2. Так же заметим, что меняется оно не чаще, чем каждые 2j / a раз. Ну а значит в периоде у нас не более 4a изменений значения, значит их все можно посчитать. Мой код
Похвастаюсь и тут, что у меня решение, которое я не успел додебагать на контесте, прошло в практис руме, и оно не использует то, что a маленькое.
Сводим к стандартной задаче подсчета суммы целых частей (a*x+b)/c по x от 0 до n-1.
А можно поподробнее, как к такой задаче свести?
Добавить 2i и посчитать сумму, деленную на 2i + 1 минус удвоенную сумму, деленную на 2i + 2 (сумма целых частей имеется ввиду, конечно)
Круто! Огромное спасибо, сдам в практис.)
Блин, надо было внимательнее читать комнату, всего 38 поинтов не хватило
что за геноцид по здаче А ? О_о
Поддержу. Есть ли какая-нибудь типичная ошибка в задаче А, которая привела к такому обильному падению задач на систестах?
Лонг-лонги может забыли?
А зачем они там? О_о
Если делать бинпоиск по ответу и смотреть, сколько очков мы можем набрать за K (1 <= K <= 10^9) раундов, то это число может не влазить в int (в первую очередь, промежуточные вычисления — понятно, что итоговое число нам и не нужно больше чем P, то есть int).
Клёво, не додумался до такого решения.
А тупая жадность разве не проще? И, кстати, там long long'и не нужны.
Я додумался лишь до динамики, полагая, что жадность упадет.
А почему так мало человек участвует? Ведь прошло 2000, ну 50 прошли в следующий раунд, но в первом всего было порядка 1300, в этом 1212. Неужели все считают, что пройдут в последнем 2C?
Ну может 1300 и 1212 в объединении дают что-то близкое к 2000? Некоторые (включая меня) не писали 2А в силу каких-то других дел, помимо олимпиад. Наверняка кто-то по той же причине не писал 2B. Но, думаю, людей которые ни в одном не поучаствуют будет мало.
О да, у меня оно было в 2А