公式

D - Red and Blue Chips 解説 by evima

We delete the last B in \(S\). Consider the string \(T\) of colors of chips in the final pile on square \(N\) from bottom to top, skipping the bottom chip.

Let \(R\) and \(B\) be the number of R and B in \(S\), respectively. Then,

\(T\) can be made to be the string R\(^{l_1}\)B R\(^{l_2}\)B R\(^{l_3}\)B\(\ldots\)R\(^{l_B}\)B R\(^{l_{B+1}}\) (where \(\sum_{i = 1}^{B+1} l_i = R\))

if and only if:

(\(\star\)) \(S\) has \(B\) disjoint (not necessarily continuous) subsequences R\(^{l_1}\)B, R\(^{l_2}\)B, R\(^{l_3}\)B, \(\ldots\), and R\(^{l_B}\)B.

Proof Let chip \(i\) be the chip starts on square \(i\), and \(X = (x_1, x_2, \ldots, x_N)\) be the sequence of chip numbers on square \(N\) in the final state from bottom to top. Here, \(X_1 = N\) always holds. Now, what can be obtained as the sequence \((x_2, x_3, \ldots, x_N)\) by the operation?

First, if you are not limited to moving piles to blue squares, all permutations of \((1, 2, \ldots, N-1)\) can be obtained as \((x_2, x_3, \ldots, x_N)\). Specifically, the only way to obtain \((x_2, x_3, \ldots, x_N)\) is to choose, for each \(i\), the square with chip \(x_{i-1}\) at the top of the pile as the destination for the \(x_i\)-th operation.

Thus, with the original restriction that you can only move piles to blue squares,

\((x_2, x_3, \ldots, x_N)\) is obtainable
if and only if:
(\(\spadesuit\)) for every \(i = 2, 3, \ldots, N\), the square with chip \(x_{i-1}\) at the time of the \(x_i\)-th operation is blue.
Here, note that once a chip is moved, it will always be on a blue square. Thus, chip \(x_{i-1}\) is on a red square if and only if chip \(x_{i-1}\) is a red chip that has never been moved. Thus, the condition (\(\spadesuit\)) is equivalent to:
(\(\clubsuit\)) for every \(i = 2, 3, \ldots, N\), if chip \(x_{i-1}\) is red, then \(x_i \gt x_{i-1}\).

\(T\) is a concatenation of \(x_2\)-th, \(x_3\)-th, \(\ldots\), \(x_N\)-th characters of \(S\) in this order, so the condition (\(\clubsuit\)) means:

the set of strings obtainable as \(T\) is equal to the set of strings obtainable by extracting \(B\) disjoint subsequences of the form R\(^{\ast}\)B from \(S\) and concatenating them in any order, followed by all remaining Rs.


Since the Rs appearing after the last B in \(S\) cannot be involved in the sequences R\(^{l_i}\)B in the above condition (\(\star\)), removing all Rs appearing after the last B from \(S\) does not change the answer to the problem. Thus, we may let \(S = \)R\(^{c_B}\)B R\(^{c_{B-1}}\)B R\(^{c_{B-2}}\)B\(\ldots\)R\(^{c_1}\)B.

When extracting \(B\) disjoint subsequences R\(^{l_1}\)B, R\(^{l_2}\)B, R\(^{l_3}\)B, \(\ldots\), R\(^{l_B}\)B from \(S\), note that it is optimal to correspond B that is more to the left in \(S\) to the B of a shorter subsequence R\(^{l_i }\)B. Then, the condition ( \(\star\)) is equivalent to the following.

\(L' = (l_1, l_2, \ldots, l_B)\), the result of sorting \(L = (l_1, l_2, \ldots, l_B)\) in descending order, satisfies the following for all \(p = 0, 1, 2, \ldots, B\):

\[\sum_{q = 0}^p l'_q \geq \sum_{q = 0} ^pc_q \tag{1}\]

(where \(l'_0 \coloneqq R - \sum_{i = 1}^B l'_i\) and \(c_0 \coloneqq 0\)).

Thus, the answer to this problem is:

the sum of \(B! / (f_0!f_1!\ldots f_i!)\), the number of sequences that are permutations of \((l'_1, l'_2, \ldots, l'_B)\), over all integer sequences of length \((B+1)\), \(L' = (l'_0, l'_1, l'_2, \ldots, l'_B)\), such that:

  • \(\sum_{q = 0}^B l'_q = R\),
  • \(l'_1 \geq l'_2 \geq \cdots \geq l'_B \geq 0\), and
  • the inequality (1) is satisfied for all \(p= 0, 1, 2, \ldots, B\).

Here, \(f_i\) is the number of occurrences of the integer \(i\) in \((l'_1, l'_2, \ldots, l'_B)\).

This can be obtained by defining the DP table \(\mathrm{dp}[i][j][k]\) as follows:

\(\mathrm{dp}[i][j][k]\): the sum of \(1 / (f_i!f_{i+1}!f_{i+2}\ldots f_R!)\) over all integer sequences of length \((j+1)\) such that:

  • \(\sum_{q = 0}^B l'_q = k\),
  • \(l'_1 \geq l'_2 \geq \cdots \geq l'_j \geq i\), and
  • the inequality (1) is satisfied for all \(p= 0, 1, 2, \ldots, j\),

and then filling it in descending order of \(i\) to find \(\mathrm{dp}[0][B][R]\cdot B!\). From each state \(\mathrm{dp}[i][j][k]\), there is a transition for each \(l\) that adds \(l\) copies of the integer \((i-1)\) to the end of \(L'\) and moves to the state \(\mathrm{dp}[i-1][j+l][k+(i-1)l]\) with the coefficient \(1/l!\).

Here, you only have to consider \(k\) that is at most \(R\), so it follows from \(R \geq k = \sum_{q = 0}^j l'_q \geq \sum_{q = 0}^j i \geq ij\) that you only have to consider \(j\) that is at most \(R/i\). Also, for \(l\), you only have to consider only \(O(R/i)\) transitions in the range \(k+(i-1)l \leq R\). Thus, the number of transitions needed is:

\[O\Big(\sum_{i = 0}^R \sum_{j = 0}^{\lfloor R/i\rfloor} \sum_{k = 0}^R \frac{R}{i}\Big) = O\Big(R^3 \sum_{i = 0}^R \frac{1}{i^2}\Big) = O(R^3),\]

and you can solve the problem in \(O(N^3)\) time.

投稿日時:
最終更新: