D - A Independent Set Editorial by evima
Hints: https://atcoder.jp/contests/agc066/editorial/9708
[1] Structure of optimal solutions
Let \(T\) denote the string after operations.
If we add a B
at the end of both \(S\) and \(T\), then \(T\) can be seen as a sequence of B
and AB
.
Let us think about the structure of the optimal \(T\) by considering the operation of swapping adjacent B
and AB
in \(T\).
Assume \(T\) is the optimal solution. For a part BAB
in \(T\) where B
and AB
are arranged in this order, if the initial position of this A
is to the left of this position, you can reduce the cost by swapping these AB
and B
. For a part ABB
in \(T\) where AB
and B
are arranged in this order, if the initial position of this A
is to the right of this position, you can reduce the cost by swapping and AB
and B
.
Then, it can be seen that in the optimal solution \(T\), when decomposed into AB
and B
, no A
passes through the positions before and after B
.
[2] Calculating the answer with dynamic programming
Based on the observations above, let us design a solution using dynamic programming.
\(\mathrm{dp}[i]\) is defined as the minimum cost to create a string of length \(i\) consisting of AB
and B
from only the first \(i\) characters of \(S\) (without swapping the \(i\)-th and \((i+1)\)-th characters).
First, if the \(i\)-th character of \(S\) is B
, there is a transition \(\mathrm{dp}[i] \leftarrow \mathrm{dp}[i-1]\).
For the part where we arrange AB
s, do the following. First, define \(\mathrm{sum}[i]\) as the number of B
s minus the number of A
s among the first \(i\) characters of \(S\). Then, when \(i<j\) and \(\mathrm{sum}[i] = \mathrm{sum}[j]\), you should make a transition from \(\mathrm{dp}[i]\) to \(\mathrm{dp}[j]\) for arranging AB
s in between.
For \(i, k, j\) such that \(i<k<j\) and \(\mathrm{sum}[i] = \mathrm{sum}[k]=\mathrm{sum}[j]\), the transition from \(\mathrm{dp}[i]\) to \(\mathrm{dp}[j]\) can be decomposed into transitions from \(\mathrm{dp}[i]\) to \(\mathrm{dp}[k]\) and from \(\mathrm{dp}[k]\) to \(\mathrm{dp}[j]\), so you only need to consider transitions where such \(k\) does not exist.
As a result, both the number of states and the number of transitions in DP are \(O(N)\).
For cases where there is no \(k\) such that \(i<k<j\) and \(\mathrm{sum}[i] = \mathrm{sum}[k]=\mathrm{sum}[j]\), it is also easy to see that for the arranged AB
s in between, there cannot be both A
s coming from the left and from the right. Therefore, the cost of each transition can be calculated in \(O(1)\) time with appropriate precomputation of cumulative sums.
posted:
last update: