Всем привет, у клавиатуры Кодер Арсений. В начале сентября я узнал о таком сайте, как Codeforces, где можно проходить соревнования и заниматься олимпиадным программированием. В своём блоге я буду каждый день делиться своими результатами участия в соревнованиях (чаще всего виртуальных).
Сегодня я принял виртуальное участие в Codeforces Round #776 (Div. 3).
Соревнование было достаточно простым и состояло из задач, которые я могу назвать классическими.
Первая задача
Решение слишком простое: символ должен стоять на нечётной позиции чтобы мы вывели YES, иначе выводим NO. Объяснение простое: мы удаляем подстроку чётной длины, а длина всей строки - нечётная. Оценка времени выполнения O(n).
Решение я сдал на второй минуте на языке программирования Python.
Вторая задача
Решение тоже достаточно простое. Нам нужно сравнить только два числа:
- r - r (mod a) - 1
- r
И всё. Выводим ответ. У этого есть математическое обоснование, оно достаточно простое.
Решал я эту задачу после задачи C, сдал на 13 минуте решение на языке Python
Третья задача
Эту задачу я решал второй. По сути я создал массив, состоящий из структур, хранящих в себе вес, координату и номер. Отсортируем по возрастанию веса (да простит меня современное общество). Сумма весов первых 2n точек будет минимальна, поэтому используем их для построения системы из 𝑛n вложенных отрезков. Сохраним веса первых 2n точек в переменной sum и удалим оставшиеся m − 2n точек из массива.
Дальше просто границами i-того отрезка будут точки с координатами i и 2n - i + 1.
И реализовываем вывод.
Сдал решение на 10 минуте на языке программирования C++
Четвёртая задача
Случаев, когда сдвигом добиться ситуации невозможно, не существует. У нас и там и там одинаковое количество возможных вариантов: n!
Далее просто смотрим массив справа налево и смотрим, какой сдвиг нам нужно сделать. Запоминаем их и выводим.
Время выполнения O(n2), сначала я подумал, что есть решение быстрее, но, посмотрев на ограничения в задаче, я без малейших раздумий сдал решение.
28 минута, C++
Пятая задача
Опять достаточно простая задача. Мы ищем экзамены с самым коротким временем между ними, и переставляем один из экзаменов:
- Либо в конец, чтобы было d - a[n] - 1 дней на отдых.
- Либо поставить в середину самого большого перерыва. Тогда время перерыва (Delay - 1) // 2.
Смотрим какой вариант выгоднее и применяем.
43 минута, C++
Шестая задача
Типичная задача о рюкзаке.
Пока у нас остаются экзамены, мы:
- Смотрим время до ближайшего дедлайна
- Смотрим, используя какие опции мы быстрее всего выполним задание с горящим дедлайном
- Считаем, сколько времени мы потратим
- Удаляем выполненное задание
- Пересчитываем времена до дедлайнов.
Всё. 1 час 10 минут, С++
Седьмую задачу я не стал решать. Обычный поиск кратчайшего пути по не взвешенному неориентированному графу.
На этом всё.