Тщательное планирование

Автор и разработчик задачи: Мария Жогова

Давайте представим разложение числа $$$a_i$$$ на сумму разрядных слагаемых: $$$a_i = a_{i, 9} \cdot 10^9 + a_{i, 8} \cdot 10^8 + \ldots + a_{i, 1} \cdot 10 + a_{i, 0}$$$, где $$$a_{i, j}$$$ — значение $$$j$$$-й цифры числа $$$a_i$$$ при нумерации с нуля от разряда единиц.

Наша задача — найти такую функцию $$$f$$$, чтобы максимизировать сумму $$$S = \sum\limits_{i=1}^n f(a_{i, 9}) \cdot 10^9 + f(a_{i, 8}) \cdot 10^8 + \ldots + f(a_{i, 1}) \cdot 10 + f(a_{i, 0})$$$. Иными словами, мы просто переписали сумму упомянутых выше выражений по $$$i$$$ от $$$1$$$ до $$$n$$$, если переназначение цифр обозначить за $$$f$$$.

Перепишем эту сумму, сгруппировав слагаемые по степеням десятки, а не по числу из набора. Для этого давайте для каждого числа $$$a_i$$$ найдем $$$$$$b_{i, k} = \sum\limits_{j=0}^9 \left(10^j \cdot \begin{cases} 1 & \text{если }a_{i, j} = k \\ 0 & \text{иначе} \end{cases} \right)$$$$$$ Такое выражение будет равно «вкладу» цифры $$$k$$$ в значение $$$i$$$-го навыка. Ясно, что $$$a_i = \sum\limits_{k=0}^9 k \cdot b_{i, k}$$$. Пусть $$$c_k = \sum\limits_{i=1}^n b_{i,k}$$$, назовем это число полным вкладом цифры $$$k$$$. Тогда

$$$$$$S = \sum\limits_{i=1}^n \left(\sum\limits_{j=0}^9 f(a_{i, j}) \cdot 10^j \right) = \sum\limits_{i=1}^n \left(\sum\limits_{k=0}^9 f(k) \cdot b_{i, k} \right) = \sum\limits_{k=0}^9 \left( f(k) \cdot \sum\limits_{i=1}^n b_{i, k} \right) = \sum\limits_{k=0}^9 f(k) \cdot c_{k}$$$$$$

Для того, чтобы получить максимально возможное значение $$$S$$$, функция $$$f$$$ должна отображать $$$l$$$ и $$$m$$$, так, чтобы $$$f(l) > f(m) \iff c_l \geqslant c_m$$$. Понятно, что если $$$f$$$ назначает цифре с не-максимальным вкладом новое значение $$$9$$$, то ее можно поменять с цифрой, вклад которой максимален, и сумма увеличится. Значит нужно распределить новые значения цифр так, чтобы наибольшие новые значения были даны цифрам, имеющим максимальный вклад.

Приведенное выше распределение не учитывает то, что после переназначения в записи навыков не должно быть ведущих нулей. В каком случае это может произойти? В том случае, когда в записи всех $$$n$$$ навыков используются 10 цифр, цифра $$$k$$$ имеет минимальный вклад и является первой в записи хотя бы одного навыка. Чтобы этого избежать, давайте отдельно рассмотрим все цифры, с которых не начинается никакой навык. Среди всех таких цифр выберем ту, которая имеет минимальный вклад, тогда функция $$$f$$$ должна заменять ее на 0. Теперь уберем из рассмотрения выбранную цифру, а значения $$$f$$$ для остальных цифр выберем так же, как в общем случае. Ясно, что такое распределение дает максимальную сумму $$$S$$$.

Все решение выглядит так:

  1. Для каждой цифры посчитаем ее вклад в общую сумму, является ли она первой в записи какого-либо навыка и общее количество различных использованных цифр в записи навыков;
  2. Если в записи всех навыков были использованы все 10 цифр, найдем ту, которая имеет минимальный вклад и с которой не начинается ни один навык. Так как мы ее заменим на 0, то в итоговой сумме она никак себя не проявит. Теперь будем считать, что она имеет вклад 0 в итоговую сумму, то есть $$$c[q] = 0$$$;
  3. Построим массив $$$g$$$, где $$$g[k] = (k, c[k])$$$. Отсортируем этот массив по не возрастанию вклада в итоговую сумму, то есть по второй компоненте каждого элемента;
  4. Ответ будем считать жадным образом. Так как мы заменяем $$$i$$$-ю цифру в порядке не возрастания вклада на цифру $$$10 - i$$$, то $$$ans = \sum\limits_{k=1}^{|g|} (10 - k) \cdot g[k][0]$$$.

Рассмотрение цифр каждого из навыков занимает константное количество действий, а всего навыков $$$n$$$, значит время работы решения — $$$\mathcal{O}(n)$$$.