D - Red and Blue Chips Editorial
by 
leaf1415
\(S\) から最後の B を削除して考えます。
最終的にマス \(N\) に出来る山の各チップの色を、山の下のものから並べた列、特に下から \(2\) 枚目以降のチップの色を並べた文字列 \(T\) を数えれば良いです。
\(S\) に含まれる R, B の個数をそれぞれ \(R, B\) とします。
このとき、
\(T\) として文字列
R\(^{l_1}\)BR\(^{l_2}\)BR\(^{l_3}\)B\(\ldots\)R\(^{l_B}\)BR\(^{l_{B+1}}\) を作れる（ただし、\(\sum_{i = 1}^{B+1} l_i = R\) ）
ことは、
（ \(\star\) ） \(S\) が
R\(^{l_1}\)B、R\(^{l_2}\)B、R\(^{l_3}\)B、\(\ldots\)、R\(^{l_B}\)Bという \(B\) 個の disjoint な（連続とは限らない）部分列を持つ
ことと同値です。
証明
初期状態でマス \(i\) にあるチップをチップ \(i\) と呼びます。最終状態でマス \(N\) にあるチップの番号を山の下のものから並べた列を \(X = (x_1, x_2, \ldots, x_N)\) とします。
このとき必ず \(x_1 = N\) です。
では、列 \((x_2, x_3, \ldots, x_N)\) としてはどのようなものが操作によって実現可能でしょうか。
まず「青いマスにしか山を移動できない」という制限がない場合は、\((1, 2, \ldots, N-1)\) の全ての順列が \((x_2, x_3, \ldots, x_N)\) として実現可能です。 具体的には、各 \(i\) について \(x_i\) 番目の操作での移動先として、「チップ \(x_{i-1}\) が山の最上に置かれているマス」を選んでいくのが \((x_2, x_3, \ldots, x_N)\) を実現する唯一の手順です。
よって、本来の「青いマスにしか山を移動できない」制限がある場合では
\((x_2, x_3, \ldots, x_N)\) が実現可能であることは、
（ \(\spadesuit\) ）任意の \(i = 2, 3, \ldots, N\) について、\(x_i\) 番目の操作の時点でチップ \(x_{i-1}\) が置かれているマスは青いマスであることと同値です。 ここで、一度でも移動されたチップは必ず青いマスにあることとに注意すると、チップ \(x_{i-1}\) が置かれているマスが赤マスであるのは、チップ \(x_{i-1}\) がまだ一度も動かされていない赤いチップであるとき、かつ、そのときに限ります。 したがって、条件（ \(\spadesuit\) ）は
（\(\clubsuit\)）任意の \(i = 2, 3, \ldots, N\) について「チップ \(x_{i-1}\) が赤ならば、\(x_i \gt x_{i-1}\) である」ことと同値です。
\(T\) は \(S\) の \(x_2, x_3, \ldots, x_N\) 文字目をこの順に並べた文字列ですから、条件（\(\clubsuit\)）は
\(T\) として得られる文字列の集合は、\(S\) から \(B\) 個のことを意味します。R\(^{\ast}\)Bの形の disjoint な部分列を抜き出してそれらを任意の順番で連結したものの後ろに残るR全てを繋げて得られる文字列の集合に等しい
ここで、\(S\) の最後の B よりも後に現れる R は、上の条件（\(\star\)） における R\(^{l_i}\)B という部分列に関与し得ないことから、
\(S\) から最後の B よりも後に現れる R をすべて取り除いても本問題の答えは変わりません。
そこで、\(S = \)R\(^{c_B}\)B R\(^{c_{B-1}}\)B R\(^{c_{B-2}}\)B\(\ldots\)R\(^{c_1}\)B として良いです。
\(S\) から \(B\) 個の disjoint な部分列 R\(^{l_1}\)B、R\(^{l_2}\)B、 R\(^{l_3}\)B、\(\ldots\) 、R\(^{l_B}\)B を抜き出す際には、\(S\) でより左にある B をより短い部分列 R\(^{l_i}\)B の B と対応させるのが最適であることに注意すると、条件（ \(\star\) ） は
\(L = (l_1, l_2, \ldots, l_B)\) を降順にソートした数列 \(L' = (l'_1, l'_2, \ldots, l'_B)\) が、すべての \(p = 0, 1, 2, \ldots, B\) で
\[\sum_{q = 0}^p l'_q \geq \sum_{q = 0} ^pc_q \tag{1}\]
を満たす（ただし、\(l'_0 \coloneqq R - \sum_{i = 1}^B l'_i, c_0 \coloneqq 0\) ）
ことと同値です。 よって本問題の答えは、
長さ \((B+1)\) の整数列 \(L' = (l'_0, l'_1, l'_2, \ldots, l'_B)\) で
- \(\sum_{q = 0}^B l'_q = R\) かつ
- \(l'_1 \geq l'_2 \geq \cdots \geq l'_B \geq 0\) かつ
- すべての \(p= 0, 1, 2, \ldots, B\) で式 (1) を満たす
ようなものすべてにわたる、\((l'_1, l'_2, \ldots, l'_B)\) の要素を並べ替えて得られる数列の個数 \(B! / (f_0!f_1!\ldots f_i!)\)の総和です。
ただし、\(f_i\) は \((l'_1, l'_2, \ldots, l'_B)\) が整数 \(i\) を含む個数です。
これは、DP テーブル \(\mathrm{dp}[i][j][k]\) を、
長さ \((j+1)\) の整数列 \(L' = (l'_0, l'_1, l'_2, \ldots, l'_j)\) で
- \(\sum_{q = 0}^B l'_q = k\) かつ
- \(l'_1 \geq l'_2 \geq \cdots \geq l'_j \geq i\) かつ
- すべての \(p= 0, 1, 2, \ldots, j\) で式 (1) を満たす
ようなもの全てにわたる、\(1 / (f_i!f_{i+1}!f_{i+2}\ldots f_R!)\) の総和
で定め、これを \(i\) の降順に埋めて \(\mathrm{dp}[0][B][R] \cdot B!\) を計算することで得られます。 各状態 \(\mathrm{dp}[i][j][k]\) からは、\(L'\) の末尾に整数 \((i-1)\) を \(l\) 個追加して状態 \(\mathrm{dp}[i-1][j+l][k+(i-1)l]\) に係数 \(1/l!\) で移る遷移を各 \(l\) について行えば良いです。
ここで、\(k\) は \(R\) 以下の範囲を考えれば十分であるため、 \(R \geq k = \sum_{q = 0}^j l'_q \geq \sum_{q = 0}^j i \geq ij\) より、 \(j\) は \(R/i\) 以下の範囲を考えれば十分です。 また、\(l\) についても \(k+(i-1)l \leq R\) の範囲の \(O(R/i)\) 本の遷移のみを考えればよいです。 したがって、必要な遷移の本数は
\[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)\]
であり、\(O(N^3)\) 時間で本問題を解くことができます。
posted:
last update: