Я занял 630-е место из ~8100 участников, поместив меня в 92-й процентиль. Надеюсь, я смогу быть в 95-м процентиле в следующем конкурсе. Мне удалось решить 3/4 задач на полную оценку, а за последний вопрос я получил частичный балл. Вот мои решения и код C++ для проблем.

Проблема 1. Маркировщик изображений

Сначала мы можем отсортировать N регионов по убыванию Aᵢ. Интуитивно лучше присвоить категории только 1 регион. Зная это, мы можем использовать жадный алгоритм; мы можем отнести регионы M-1 с самым высоким Aᵢ к категориям M-1. Затем все оставшиеся регионы попадают в одну категорию. Временная сложность — O(N logN).

Задача 2. Максимальный выигрыш

Вам нужно найти максимальное количество баллов, которое вы можете заработать, выбирая 0 ~ K местоположений из массива A и B. Это связано с тем, что когда вы выбираете i местоположений из A, вам нужно выбрать K-i местоположений из B. Затем вы можете перебрать 0 ~ K, и найти наилучшую комбинацию из массивов A и B.

Чтобы найти максимальное количество баллов, достижимое при выборе i мест из массива, вы можете использовать аналогичный метод. Если вы выбираете j мест в начале, вам нужно выбрать i-j в конце. Для этого я использовал prefixsum, получив временную сложность O(K²).

Проблема 3. Сенсорная панель ввода

Вам нужно использовать динамическое программирование для этой проблемы. Я определил dp[i][j] как минимальное время, необходимое для ввода i-го символа, который заканчивается в позиции j. Наивным решением было бы найти все позиции, в которых заканчивается i-1-й символ (назовем это k), и обновить dp[i][j] для dp[ я-1][к]. Однако временная сложность этого решения составляет O(N·M²).

Чтобы решить последний тестовый пример, вам нужно сделать наблюдение, что всегда оптимально набирать следующую клавишу, ближайшую слева или ближайшую справа от текущей клавиши. Это снижает временную сложность до O(N·M), позволяя решить все тестовые случаи.

Задача 4. Подозреваемые и свидетели

Тестовый пример 1 решить довольно просто, потому что есть только один похититель. Вам просто нужно вычесть общее количество людей на количество людей, которые не были упомянуты. Это потому, что если А упоминается кем-то другим, вы не можете быть уверены, что А не крадет. Временная сложность решения первого теста равна O(N).

Я обновлю этот пост, когда решу второй тестовый пример для последней проблемы.