Lets discuss problems here.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 02:34:44 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
По-моему, 500 как раз из разряда тех задач, о которых говорили в этом топике. Не знаю, как у остальных, а у меня всегда были проблемы с доказательством подобного рода жадностей. Это уже не первый раз на топкодере, когда я понятия не имею, как решать 500-ку, потом вижу что народ ее сдает очень активно и у топов за нее 460+ и я сдаю самую правдоподобную на мой взгляд жадность, которую можно написать за 5-10 минут.
Кстати, а как там строго доказывать решение?
Во-первых, пусть мы уже переставили буквы. Тогда нам надо назначить первой буквой в перестановке алфавита первую букву слова (если у нас есть уникальная буква, то мы просто можем поставить ее на первое место и выиграть, а иначе нас победят). Тогда надо все копии этой буквы поставить в начало, так как лексикографическое сравнение — линейный порядок, а так мы добьемся минимального из возможных префикса. Теперь есть слова, которые мы точно победили, а есть те, которые еще не победили. Ну и так далее
А если у нас есть несколько кандидатов на первую букву, то какой выбирать?
А неважно. Мы можем их взять в любом порядке и выживут только те соперники, которые выживут после каждого
Да, теперь понял. На контесте завис именно на этом моменте и долго не решался кодить.
Мне моё объяснение нравится чуть больше Егоровского :)
Пусть мы уже переставили алфавит. Тогда ясно, что каждое слово (и наше, и противников) нужно отсортировать в соответствии с этим порядком, то есть фактически заменить его на последовательность (количество 1-й буквы) (количество 2-й буквы) ..., которые опять же сравниваются лексикографически.
Ну а дальше ясно, что нужно брать буквы так, что на очередном шаге мы берем ту, которой у нас больше либо равно всех оставшихся (иначе мы сразу проиграем), и выкидывать те, где у нас больше (потому что у них уже выиграли). А тогда ясно, что если букву можно взять, то взять её прямо сейчас ничем не плохо.
Мы долгое время пытались решить эту задачу без ограничения на равную длину строк. Может, есть идеи как её решать в этом случае?
Мне кажется, тут надо один момент уточнить. В общем случае (когда строки не равной длины) может оказаться, что мы выбрали символ, которого в нашей строке не менее чем в каждой другой, но он был для какой-то другой непобежденной строки последним. Тогда она очевидно лексикографически меньше нашей и мы проиграем. Но когда строки равной длины, такой сценарий невозможен, так как тогда в той строке какого-то другого символа было больше и мы её бы уже до этого выкинули.
LOL.. nice one