Сегодня в 21:00 MSD состоится Single Round Match 527. Так как темы до сих пор почему-то не было, я решил создать.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
7 | adamant | 154 |
9 | Um_nik | 152 |
10 | djm03178 | 146 |
Сегодня в 21:00 MSD состоится Single Round Match 527. Так как темы до сих пор почему-то не было, я решил создать.
Название |
---|
А какую еще ему дать?
Обязательно бы написал TC, и так уже из-за сессии дофига пропустил SRM'ов.(
Ребят, приношу извинения за тупость (может быть) . На ТС впервые.задача 550, почему в примере {1, 3, 0} ответ 8, а не 12 ?мы ведь можем соединить все вершины (ака квадрат получится)...Ну я просто смотрел, похоже ли решение на моё :)
Это что-то типа
"Все неправильные решения челенджит Петр, остальным автоматически выставляется Passed System Tests"?
Заметим, что сумма степеней всех вершин у нас всегда 2*(n-1). Так как вершин всегда n, то наша задача сводится к рюкзаку. f[i][j] равняется максимальной сумме, когда у нас уже i вершин расставлена и сумма степеней у них равна j.
Ответ = f[n][2*(n-1)]
У меня почти вся комната так решала, и мой сокомандник, который красный :)
UPD: Мой сокомандник все-таки по-другому решал эту задачу :)
10000 и 5 маленьких чисел
а у меня одномерная динамика в 250
пусть dp[k] - оптимум для дерева из k вершин
поскольку у нас дерево, хоть один лист у него да есть
возьмем любой лист и будем в цикле добавлять к нему вершины от 1 до тех пор, пока количество вершин в дереве не будет равняться N
при этом у нас степень листа изменится с 1 на i + 1 и добавится i новых листьев
что в конечном итоге даст нам: dp[k + i] = max(dp[k + i], dp[k] + (cost[i] - cost[0]) + cost[0] * i)
ну и начальная инициализация dp[2] = cost[0] * 2
Upd. Такое решение ниже описали, сорри)
Нет, я динамику и написал. Может, это лажа, но у меня динамика находит разложение числа 2n - 2 на n слагаемых, каждое из которых лежит на отрезке [1, n - 1]. Как по таким весам дерево строить? Я ни способ найти не могу, ни контрпример.
k - степень корня, той вершины к которой мы сейчас будем детей подвешивать, n - количество вершин в данном поддереве не считая корня. перебираем по i количество вершин в поддереве первого ребенка D(i - 1, 1) - динамика для этого поддерева, прибавляем динамику остальных детей D(n - i, k + 1) - уменьшаем кол-во вершин, увеличиваем степень корня
Ну а ответ на задачу это D(n - 1, 0). ну и запоминание нужно прикрутить к этой динамике.
Мда... решать 275-ку 20минут, затем открыв 475-ку, мгновенно ее решив и еще минут за 5 написав хз сколько ловить опечатку в дфс-е (вместо u[i] было написано u[v]), а за оставшиеся полчаса решить, написать и (как мне кажется, с вероятностью 99%) добедагать 1050 с точностью до нескольких символов в одной строчке - столь эмоционального SRM-а у меня еще не было, жаль, что намного больше отрицательных эмоций, да и еще с красным цветом чуть было не попрощался.
Вот что я писал в 1000-ке.
Пусть V1<V2<...<Vn достоинства монет, Sum - необходимая сумма. Пусть Si=Sum/Vi.
Общая идея такова - в любом множестве сначала склеим как можно больше монет V1 в монеты V2, потом склеим как можно больше монет V2 (с учетом полученных из склеивания V1) в монеты V3, и т.д. (кстати, в конце мы получим всегда один и тот же набор монет).
Считать ответ мы будем разворачивая этот процесс. Будем считать динамику D[i][j] - где 1<=i<=n && 0<=j<mod и D[i][j] - число множеств (по модулю 10^6+3) которые могли получить после i-1 склеивания (т.е. в последний раз мы склеивали V(i-1) в Vi) в которых число монет Vi дает остаток j. Осталось заметить, что в любом таком наборе число монет вида Vi равняется (Si%(V[i+1]/V[i]))+t*(V[i+1]/V[i]) - где t - это число монет V[i+1], склеенных из монет Vi. Причем число монет V[i+1], которые мы можем расклеить ограничено лишь их общим числом, причем все эти способы дают различные итоговые множества, т.е. если r=Si%(V[i+1]/Vi), d=V[i+1]/V[i], то D[i][j] - сумма некоторых D[i+1][что-то], причем D[i+1][k] участвует в качестве слагаемого в выражении D[i][j] тогда и только тогда, когда существует h<=k : j=(h*d+r)%mod. Осталось подсчитать суммы на суффиксах массивов D[i], чтобы пересчитывать каждый новый слой за линию, ну и заметить что все переходы от формул, которые очевидны в целых числах к кольцу остатков корректны.
Upd. Ну, и конечно же, хранить достаточно только один слой и динамика получается с линией памяти.
Upd.2. Да, это действительно работает. Очень обидно сливать 3-е место из того, что не хватило пары минут(