Вот и начинается СРМ 572. Желаю удачи и после матча всем предлагаю обсудить здесь задачи.
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
4 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 26.11.2024 20:21:38 (h2).
Десктопная версия, переключиться на мобильную.
При поддержке
АААргх. Понятно конечно что я сам себе злой Буратино, но если уж делать анонсы, то можно их делать и несколько заранее)
Как решать Div2 1000? Понятно что там нужна динамика и комбинаторика. Но из-за модуля я никак не могу нормально динамику организовать из обычного алгоритма без модуля.
После конца срма будет интересно узнать, заходит ли в 500 див1 перебор первых 6 символов, а для последних трёх прекалк(тут двух лонгов для хранения каждой из комбинаций должно хватать)?
Решение — это почти то, о чем вы говорите, а именно — MeetInTheMiddle. Переберем первую половину ответа. Переберем вторую половину ответа отдельно. Для каждого варианта и каждого запроса посчитаем, сколько символов матчится. Сохраним результаты (например, как string, где на i-том месте записано, сколько символов матчится у текущего варианта с i-тым запросом) в map или hashtable.
Теперь, если мы зафиксировали какой-то вариант для первой половины ответа, то мы точно знаем, сколько нам нужно добрать поматчившихся символов для каждого запроса во второй половине ответа. Посчитаем нужный нам результат во второй половине ответа, посмотрим, сколько таких результатов есть в map или hashtable.
Понятно объяснил?
Да, спасибо. Почему-то казалось, что делить пополам не заходит, так как вторую половину сложно искать, и надо подбирать баланс.
Расскажите, пожалуйста, кто знает, как решать 1000? :)
Была такая идея, не заработало на 6 сэмпле. Где-то баг.
Посмотрим на первую букву, которая куда-то перешла. Переберем как ее перевести — или по часовой стрелке или против. Тогда все остальное задается однозначно. Посмотрим что получится. Выберем лучшее из двух.
Не совсем однозначно. Например, когда у нас все буквы переходят в одну, каждую можно вести в любом направлении.
Слова одинаковые => 0
В goal 26 букв => -1
Всё идёт в одну букву => надо перебрать сколько букв сдвигать вправо а сколько влево.
А теперь самое интересное.
У нас есть список отрезков, переходящих в какие-то буквы.
Очевидно, как вычислить цену перехода отрезок в букву без учёта циклов.
Сам алгоритм: внешний цикл — это перебор относительного сдвига (+0, +26, -26) первого отрезка относительно первой буквы, а внутренний — это проход по всем отрезкам. Если так получилось что во внутреннем цикле мы намотали более одного круга по goal, то решения нет.