| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 153 |
| 2 | nik_exists | 151 |
| 3 | maroonrk | 150 |
| 4 | maspy | 149 |
| 5 | AmShZ | 146 |
| 6 | Um_nik | 143 |
| 7 | Errichto | 139 |
| 8 | adamant | 135 |
| 9 | BledDest | 134 |
| 10 | cry | 130 |
| Название |
|---|



Как решать 500? Написал тупую динамику без всяких отсечений, её, разумеется, сломали (правда, с третьей попытки).
Я перебирал циклический сдвиг. Дальше решал задачу для отрезка динамикой z[i][j] — где стоим и сколько должны начиная с нашей позиции выкинуть.
Сколько выкинуть же всегда определено уровнем карты?
У нас могут быть открыты несколько карт.
Посмотрим на итоговый ответ. Понятно, что в нём будет такое i, что среди i + 1, ..., i + li - 1 нет взятых в ответ элементов (в начальной конфигурации; просто возьмём какой-то элемент и пойдём от него направо, пока не упрёмся в требуемый, круг мы сделать не можем). А значит, перебираем элемент-"разрез" и проходимся тупой динамикой с конца разрезанного круга.
не очень понятно, что за тупая динамика?
Ну d[i][j] — мы находимся на i'ом с конца элементе и у нас "в запасе" есть j элементов для удаления; переходы — либо i + 1, j + 1, либо i + 1, j + 1 - li с увеличением урона на d[i]. Но если немного подумать, эта динамика упрощается до выбора элементов с суммой li не больше n, как пишут ниже; т.к. любое такое подмножество можно набрать, пройдя справа налево.
Можно просто выбирать набор карточек с сумой уровней не больше n, c максимальным уроном.
Рюкзак, где вес вещи — li, а стоимость — di. Нужно набрать вещей с суммарным весом не более N.
У меня в комнате один из участников посабмитил по easy перебор. Я долго думал как его почеленджить так и не понял. Passed system tests.
Это странное чувство, когда на вторую задачу уходит меньше времени, чем на первую...
У меня другое чувство, когда на третью уходит меньше времени, чем на вторую :(
UPD: А потом еще другое чувство, когда видишь решение в две строчки по 500
А как решать 950?
Расскажу свое решение, не претендую на оптимальность асимптотики и времени написание кода. :) Придумал на раунде, но написать не успел и досдал только что в практисе.
Рассмотрим нашу решетку как детерминированный конечный автомат над алфавитом {L, R, U, D}. Состояниями будут вершины сетки, в которых нет препятствия, а также будет сток, который будет допускающим состоянием. Переходы из состояния по каждой букве ведут в ту вершину, куда сместилась бы монетка на этой позиции при заданном действии. Если она падает со стола, направим ребро в сток.
Когда положение монет хорошее? Когда есть 2 монеты, которые лежат на неэквивалентных состояниях (ибо есть различающая их строка, а значит, одна упадет, а другая -- нет). Посчитаем, сколько таких расстановок (точнее, посчитаем все и вычтем плохие). Плохие — это когда монетки лежат на позициях, соответствующих эквивалентным состояниям. Вычтем в таком случае из ответа 2cnt - 1, где cnt -- количество вершин в каком-то классе эквивалентности. Итого,
, где cnti — количество вершин в i классе эквивалентности вершин в автомате, и
.