出来る操作は、長さ \(2\) の操作が \(3\) 種類 (BA → AB / CA → AC / CB → BC) と長さ \(3\) の操作が以下の \(3\) 種類です。

• BCA → ABC
• CAB → ABC
• CBA → ABC

到達可能性は長さ \(2\) の操作のみを考えればよいです。長さ \(3\) の操作の導入で操作回数がどうなるかがこの問題の本質です。

まず、長さ \(3\) の操作で必ず CA が \(1\) 組swapされていることに注目すると、(長さ \(3\) の操作 + 操作 CA -> AC) の操作回数の総和は常に一定であることが分かります。言い換えると、この問題は BA → AB と CB → BC がコスト \(1\) で、他の操作はコスト \(0\) である、とみなすことが出来ます。

そして、各 B について「自分より右側の A の個数」「自分より左側の C の個数」を管理することを考えると、B を二次元格子点上を動く \(N\) 個の駒として考えることが出来ます。

これを踏まえると、この問題は \(2\) 次元平面上の多品種フローのような問題と考えることが出来ます。

基本的に各 B はコスト \(1\) で距離 \(1\) を移動しなければならないのですが、各格子点(= CA ペア)ごとに、高々 \(1\) つまで B の移動を巻き込むことができます。

グラフが平面的なので、フローのパス同士が交差したら交換可能なことに注目すると、結局すべての条件を多品種ではないフロー、つまり最小費用流として書き下すことが出来ます。

より詳しくは、A / B / C を \(N\) 個ずつ含む文字列を、以下の手続きで二次元格子点上のヤング図形と、その境界上の駒に対応付けます。

• \((N, 0)\) からスタートし、文字列の文字を最初から順に読む
• A が出たら \(x\) を \(-1\)、C が出たら \(y\) を \(+1\) する。
• B が出たら現在地点に駒を \(1\) つ置く (同じ個所に駒が複数置かれることもある)

これで、\(S\) をヤング図形と駒に対応付け、操作によって \(T\) (に対応するヤング図形と駒の状態)へと変化させる問題だと考えます。

各操作で折れ線と駒がどのように変化するかを考えると、先述のフローで得られた解が、「折り返すべき折れ線のうち最も \((x + y)\) が大きい箇所に注目し、必要ならば BA → AB / CB → BC を行った後、その CA をswapするような操作を行う」ことを繰り返すことで達成可能なことが分かります。

計算量は \(O(N^2)\) 頂点 \(O(N^2)\) 辺のグラフに \(O(N)\) フローを流すことになり、\(O(N^3 \log N)\) となります。

writer解