辺を張る順を固定して、得られる \(A\) の条件について考えます。

\(A\) に含まれる \(\text{1}\) の個数を \(k\) とします。 \(i\) と \(j\) が連結であるような \(i,j(1 \leq i<j \leq N)\) の組の個数を \(c\) と表します。 始めて \(c\) が \(k\) 以上になる直前の \(c\) を \(x\)、直後の \(c\) を \(y\) と置きます。

このとき、\(A\) の条件は、\(x+1\) 番目の \(\text{1}\) よりも左にある \(\text{0}\) の個数 が \(y-k\) 以上になることです。 また、\(B\) を特別な文字列にするのに必要な操作回数は、\(x+1\) 番目の \(\text{1}\) よりも右にある \(\text{0}\) を条件が満たされるまで左に動かすのにかかる操作回数です。

\(y\) の値を固定して考えると、\(x\) は \(c\) 未満でできるだけ大きい方がいことがわかります。

\(c\) が \(k\) 以上になるときにマージされてできる連結成分のサイズが \(N-n\)、それに含まれない頂点で連結なものの組を \(m\) とすると、\(y\) が決まり、最適な \(x\) も決まります。 \(n\) 頂点を使って連結な \(2\) 頂点の組を \(m\) 個にできるような最小の \(n\) を \(dp\) で求め、各 \(\text{0}\) よりも左にある \(\text{1}\) の個数の累積和などを持つと、\(n,m\) ごとに必要な操作回数を求めることができます。

計算量について考えます。 \(x\) が最適となるような \(N-n\) 頂点の分け方は、\(m\) に対して単調性があるので、尺取り法により、各 \(n,m\) について \(O(N^3)\) で求まります。 また、それ以外も \(O(N^3)\) で計算できます。