83.md (5785B)
1 Source: https://codeforces.com/blog/entry/1976 2 3 # Задача А (Div-2). Игрушечные армии 4 5 Утверждение первое: пусть пусть первым ходом было убито *x* солдат, а вторым *y*, тогда третьим ходом количество убитых будет равно *min*(*n* - *x*, *n* - *y*) = *n* - *max*(*x*, *y*). Значит, общее количество убитых будет равно *x* + *y* + *n* - *max*(*x*, *y*) = *n* + *min*(*x*, *y*), и именно эту величину нам нужно максимизировать. Рассмотрим ограничения на эти переменные: 0 ≤ *x* ≤ *n*, 0 ≤ *y* ≤ *n* - *x*. Значит, нам нужно найти максимум функции *f*(*x*, *y*) = *n* + *min*(*x*, *y*) в этой области. Понятно, что если мы скажем, что *y* = *n* - *x* (то есть для *y* примем крайнее положение), то ответ не уменьшится, а значит, можем свести нашу функцию к *f*(*x*) = *n* + *min*(*x*, *n* - *x*) на отрезке [0, *n*]. Очевидно, максимум этой функции равен 3· *n* / 2 в точке *x* = *n* / 2. 6 7 **Ответ: 3· *n* / 2.** 8 9 # **Задача E (Div-1). Две последовательности** 10 11 Для начала, попробуем нашу задачу решить, не задумываясь об асимптотике. Рассмотрим динамическое программирование, где состояние - это пара (*i*, *j*) (а значение - это минимальная суммарная длина двух последовательностей), которое означает, что первая последовательность у нас заканчивается строкой *i*, а вторая - строкой *j*. Переходы тогда выглядят следующим образом: мы должны взять элемент с номером *v* = *max*(*i*, *j*) + 1 и добавить в одну из последовательностей, таким образом перейти в новые состояния (*i*, *v*) и (*v*, *j*), пересчитав нужным образом значение. 12 13 Выпишем более формально, но теперь использовав динамическое программирование "назад", считая, что *i* > *j*: 14 15 ``` 16  17 ``` 18 19 Теперь придумаем окончательное решение. В силу постановки нашей задачи, можно задачу свести к другой динамике - *D*(*i*, *s*), где состояние означает, что одна из последовательностей заканчивается на строку номер *i*, а вторая - на саму строку *s*, причем, заметим, что под строкой *s* будем подразумевать не только строки из входных данных, но и **все их суффиксы длиной от 0 до *l***. Вспомним, что строки у нас бинарные длиной не более 20 символов, а это значит, что строки можно закодировать двоичными числами, в этом случае строка кодируется парой - длиной и самим числом (это строка, если ее интерпретировать как двоичную запись; эта тонкость нужна, т.к. в строках, возможно, присутствуют лидирующие нули, в этом случае разные строки будут переводится в одно и то же число), причем, общее количество пар будет не более 221. 20 21 Будем итерироваться по *i* и поддерживать наш массив со значениями динамики (одномерный, размером 2*l*). При переходе, нам нужно обновить его в соответствии с формулами выше: по первой нам нужно ко всем элементам массива прибавить величину f(i - 1, i) - это можно сделать, поддерживая дополнительную переменную *balance* и прибавлять к ней (таким образом, реальное значение элемента *i* будет равно *balance* + *d*[*i*], хотя в самом массиве значение хранится будет *d*[*i*]). А второе обновление еще проще, мы должны перебрать какой длины у нас будет наложение строки на последовательность, взять соотвествующее значение в массиве, и по всем таким перебираемым величинам взять минимум и записать его в соответствующее место в массиве. 22 23 Реализовать этот алгоритм можно за асимптотику *O*(*n* * *l*) с требуемой памятью *O*(*n* + 2*l*).