\(A_i=(S_1,S_2,\ldots,S_i\) の中の 0 の個数 \()\) 、\(B_i=(S_1,S_2,\ldots,S_i\) の中の 1 の個数 \()\) とします。(ただし、\(A_0=B_0=0\) とする)

ある整数の組 \((l,r)\) \((1 \leq l \leq r \leq N+1)\) について、 \(1 \leq i \leq N\) を満たす整数 \(i\) に対し、\(S_i=\) 1 と \(l \leq i < r\) は同値である状態にするために必要な操作回数が何回かを考えます。

まず、\(l \leq i <r\) を満たす \(i\) \((1 \leq i \leq N)\) のうち \(S_i=\) 0 であるものの個数分の操作回数は必要です。これは \(A_{r-1}-A_{l-1}\) です。さらに \(i<l\) もしくは \(r \leq i\) を満たす\(i\) \((1 \leq i \leq N)\) のうち \(S_i=\) 1 であるものの個数分の操作回数も必要です。これは \(B_N-(B_{r-1}-B_{l-1})\) です。 逆に、\(B_N+A_{r-1}-B_{r-1}-A_{l-1}+B_{l-1}\) 回の操作で十分であることがわかります。

つまり、あり得るすべての整数の組 \((l,r)\) \((1 \leq l \leq r \leq N+1)\) について \(A_{r-1}-B_{r-1}-A_{l-1}+B_{l-1}\) の最小値が求まれば答えも求まります。\(C_i=A_i-B_i\) とすると操作回数は \(C_{r-1}-C_{l-1}\) になります。数列 \(C\) に対する \(C_{r-1}-C_{l-1}\) の最小値は \(\displaystyle \min_{1 \leq l \leq r \leq N+1} C_{r-1}-C_{l-1}=\min_{1 \leq r \leq N+1} (C_{r-1}-\max_{1 \leq l \leq r}C_{l-1})\) と表せることから、 \(r=1,2,\ldots,N+1\) の順で暫定の \(C\) の最大値を保持していくことで時間計算量 \(\mathrm{O}(N)\) で計算することができます。

よって、この問題全体でも時間計算量 \(\mathrm{O}(N)\) で解くことができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    vector<int> c(n + 1);
    for (int i = 0; i < n; ++i) {
        c[i + 1] = c[i] + (s[i] == '0' ? 1 : -1);
    }
    int sum = count(s.begin(), s.end(), '1');
    int ma = 0;
    int res = 0;
    for (int i = 0; i <= n; ++i) {
        res = min(res, c[i] - ma);
        ma = max(ma, c[i]);
    }
    cout << sum + res << endl;
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}