412A - Плакат

В данной задаче одно из оптимальных решений следующее. Если k - 1 ≤ n - k, то подвинем сначала лестницу на k - 1 позицию влево. Затем n - 1 раз проделаем пару операций: нарисуем i-ый символ названия и подвинем лестницу вправо. После этого нарисуем последний символ названия. Если же k - 1 > n - k, то подвинем сначала лестницу вправо на n - k позиций. Далее также будем рисовать символ и передвигать лестницу влево, и последним действием нарисуем первый символ названия. Суммарное количество требуемых операций равно min(k - 1, n - k) + 2·n - 1.

412B - Настройка сети

В этой задаче нужно было отсортировать массив по невозрастанию и вывести k-ый элемент. Также ограничения позволяли решать следующим образом. Переберем ans — величину ответа и посчитаем, сколько компьютеров уже имеют скорость не меньшую ans. Если их не меньше k, то такой ответ нам подходит. Среди всех подходящих ответов выберем максимум, это и будет искомой величиной.

412C - Строка-шаблон

Будем искать требуемый шаблон посимвольно. Рассмотрим i-ый символ. Если в заданных строках на i-ых позициях есть хотя бы два различных символа, отличных от «?», то в ответе на i-ой позиции должен стоять «?». Если на i-ой позиции во всех строках стоят «?», то мы можем записать в ответ любой символ в качестве i-го. Очевидно, лучше записать не «?», а какую-нибудь букву, например «x». Остается случай, когда на i-ых позициях стоят «?» и какая-то одна и та же буква. Тогда нужно определить, что это за буква и добавить ее в ответ.

412D - Выдача премий

Будем строить искомую перестановку по индукции добавляя по одному сотруднику. Пусть мы уже определили порядок первых k сотрудников: a₁, a₂, ..., a_k. Скажем, что k + 1-ый будет идти за a_k-ым. Если a_k-ый сотрудник должен денег k + 1-ому, то поменяем им местами (получим перестановку a₁, a₂, ..., a_k - 1, k + 1, a_k). Если и a_k - 1-ый сотрудник должен k + 1-ому, то поменяем и их местами, и так далее. Если же все из первых k сотрудников должны k + 1-ому, то он окажется в самом начале перестановки. При аккуратной реализации данный алгоритм будет работать за время O(m), где m — количество отношений долга.

412E - Е-mail адреса

Переберем позицию i такую, что s_i = «@». Посчитаем количество подстрок, являющихся корректными адресами, у которых символ «@» — это s_i. Будем идти влево от i до тех пор, пока не встретим «@» или «.» — символы, которые недопустимы слева от «@». Посчитаем cnt сколько букв на пройденном отрезке — с них могут начинаться корректные адреса. Теперь будем двигаться вправо от i пока будут идти цифры или буквы. Если после этого строка закончилась или следует "@" или "_", то корректные адреса уже не могут получиться. Если же далее идет «.», то пройдем вправо от нее до тех пор, пока встречаются буквы. В каждой из этих букв может закончится корректный адрес, поэтому каждый раз нужно прибавлять к ответу cnt. В описанном выше решении "пройдемся" означает "перебираем циклом". Это можно делать, т.к. в результате по каждому символу мы пройдем не более 2 раз. Итого асимптотика решения O(n).