Розворот ABC#11816

Розворот ABC (Розбір)

Автор задачі:	Антон Тригуб
Задачу підготували:	Роман Піцура
Розбір написали:	Роман Піцура, Ігор Баренблат

10pt

Блок 1

У цьому блоці відповідь може бути 0 або 1. Щоб його розв'язати, потрібно перевірити, чи можливо виконати хоча б одну операцію. Якщо так — вивести 1, інакше — 0.

Необхідно з'ясувати, чи існує таке $i$ , що підрядок $s_{i} s_{i + 1}$ s_is_{i+1} дорівнює одному з трьох: AB, BC або CA.

Блок 2

У цьому блоці потрібно перебрати всі можливі рядки довжини до 3 і побудувати дерево розгалужень.

Блок 3

У цьому блоці рядок складається лише з символів A та B, отже, можлива тільки одна операція — над підрядком AB.

Фінальний вигляд рядка — це всі B ліворуч, а всі A праворуч: BB...BBAA...AA, бо більше неможливо виконати жодну операцію.

Щоб порахувати кількість операцій, для кожного символу A потрібно підрахувати кількість B, що йдуть після нього, та просумувати для всіх A.

Блок 4

Для рядка виду AA...AABB...BBCC...CC, нехай $n$ — кількість A, $m$ — кількість B, $k$ — кількість C.

Вигідно або замінити всі A та B, або всі B та C.

Відповідь: $max (n \cdot m, m \cdot k)$ \max(n \cdot m, m \cdot k).

Блок 5

Погрупуємо однакові підрядки символів у початковому рядку — вони виконуватимуть операції разом.

Якщо підрядок CA ніколи не з'являвся, він і не з'явиться після жодної кількості операцій.

Доведення: якщо припустити, що CA з'явився, то до цієї операції рядок мав містити CBA або AC, але з жодного з цих рядків не утворюється CA.

Можливі лише операції над AB та BC. Для кожного символа B розглянемо такі випадки:

1. B має зліва лише A: взаємодіє з усіма A до першого C зліва.

2. B має справа лише C: взаємодіє з усіма C до першого A справа.

3. B має A зліва і C справа: обираємо максимум з випадків 1 і 2.

Блок 6

Якщо довжина рядка $\leq 12$ , можна запускати повну рекурсію.

Якщо операції виконати неможливо — відповідь 0.

Інакше перебираємо всі можливі операції, запускаємо рекурсію для кожного варіанту і вибираємо максимальну відповідь.

Складність: $O (n \cdot 3^{n})$ O(n \cdot 3^n), оскільки кількість станів — $3^{n}$ 3^n, і з кожного стану — до $n$ переходів.

Блок 7

Щоб розв'язати цей блок, попередньо порахуємо відповідь для всіх $3^{n}$ 3^n станів (як у блоці 6).

Після цього на кожен запит відповідатимемо за $O (1)$ .

Блок 9

Погрупуємо однакові підрядки символів у початковому рядку — вони діятимуть разом.

Результуючий рядок матиме вигляд ...ACBACBACB....

Введемо $d p [перший символ] [суфікс]$ dp[\text{перший символ}][\text{суфікс}] — відповідь для суфікса, якщо перший символ у результаті — вказаний.

Тоді шукаємо $max (d p [^{'} A^{'}] [0], d p [^{'} B^{'}] [0], d p [^{'} C^{'}] [0])$ \max(dp['A'][0], dp['B'][0], dp['C'][0]).

Переходи в $d p$ , для прикладу $f i r s t_sy mb o l = A$ first\_symbol = \texttt{A} (аналогічно для інших):

- Якщо $s [i] = A$ s[i] = \texttt{A}, то $d p [A] [i] = max (d p [A] [i + 1], d p [C] [i + 1])$ dp[\texttt{A}][i] = \max(dp[\texttt{A}][i+1], dp[\texttt{C}][i+1]) (після A не може бути B). - Якщо $s [i] = B$ s[i] = \texttt{B}, то $d p [A] [i] = - \infty$ dp[\texttt{A}][i] = -\infty. - Якщо $s [i] = C$ s[i] = \texttt{C}: - Якщо далі йде B або кінець рядка, то $d p [A] [i] = - \infty$ dp[\texttt{A}][i] = -\infty. - Якщо рядок виглядає як CACACACA[C], то переміщуємо всі A ліворуч:

$d p [A] [i] = value_of_swapping_all_A_to_left$ dp[\texttt{A}][i] = \text{value\_of\_swapping\_all\_A\_to\_left}

- Якщо рядок виглядає як CACACACACB...:

$d p [A] [i] = value_of_swapping_all_A_to_left + d p [B] [B ...]$ dp[\texttt{A}][i] = \text{value\_of\_swapping\_all\_A\_to\_left} + dp[\texttt{B}][B...]

- Якщо рядок має вигляд CACACACAB..., то:

$d p [A] [i] = max (value_of_swapping_all_A_to_left + d p [B] [B ...],$ dp[\texttt{A}][i]= \max(\text{value\_of\_swapping\_all\_A\_to\_left} + dp[\texttt{B}][B...], $value_of_swapping_bold_A_to_left + d p [B] [A B ...]$ \text{value\_of\_swapping\_bold\_A\_to\_left} + dp[\texttt{B}][AB...] $)$