[1] \(1\) の個数で場合分けする

\(S\) に含まれる 1 の個数を \(k\) 個とします。

操作によって、\(k\) がどのように変化するか考えると、\(0,+2,-2\) のいずれかなので、\(k\) が奇数の場合は条件を達成できません。以下偶数の場合を考えます。

• \(k=0\) の場合

明らかです。

• \(k\geq 4\) の場合

表向きのコインの番号を 左から順に \(x_1,x_2,\ldots,x_k\) とします。 このとき、コイン \(1\) とコイン \(x_{\frac{k}{2}+1}\) に操作し、コイン \(2\) とコイン \(x_{\frac{k}{2}+2}\) に操作し、と順に行うことで、\(\frac{k}{2}\) 回の操作で条件を達成可能です。

• \(k=2\) の場合

表向きのコインが隣接していない場合、答えは \(1\) です。 以下、隣接している場合を考え、左にあるコインの番号を \(x\) とします。

\(x\geq 3\) の場合、コイン \(1\) と \(x\) に操作 \(\to\) コイン \(1\) と \(x+1\) に操作 とすることで \(2\) 回の操作で条件を達成可能です。

また、\(x+1\leq N-2\) の場合も、コイン \(x+1\) と \(N\) に操作 \(\to\) コイン \(x\) と \(N\) に操作 とすることで \(2\) 回の操作で条件を達成可能です。

これら二つの条件をどちらも満たさないのは、\(x<3\) かつ \(x+1 > N-2\) のときで、これは \(N=3,4\) のときに限られます。

\(N=3\) のとき、\(S\) は 011 または 110 ですが、コイン \(1\),\(3\) 以外に操作が出来ないことから、条件は達成不可能です。

\(N=4\) かつ \(x<3\) かつ \(x+1 > N-2\) を満たす \(S\) は 0110 です。このとき、\(3\) 回の操作で条件を達成可能です。（方法：0110\(\to\)1111\(\to\)0101\(\to\)0000）また、\(2\) 回の操作で条件を達成不可能なことも、全探索により示せます。

これらの条件は全て \(\mathrm{O}(N)\) で判定可能です。

---

[2] 実装例

C++:

#include <bits/stdc++.h>
using namespace std;

int solve() {
    int n;
    string s;
    cin >> n >> s;
    int one = count(s.begin(), s.end(), '1');
    if(one & 1) return -1;
    bool adj = 0;
    for(int i = 0; i < n - 1; i++)
        if(s[i] == '1' and s[i] == s[i + 1]) adj = 1;
    if(one != 2 or !adj) return one / 2;
    if(n == 3) return -1;
    if(n == 4 and s == "0110") return 3;
    return 2;
}

int main() {
    int t;
    cin >> t;
    while(t--) cout << solve() << endl;
}

Python:

def solve():
    n = int(input())
    s = input()
    k = s.count("1")
    if k & 1:
        return -1
    adj = s.count("11")
    if k >= 4 or k == 0 or not adj:
        return k // 2
    if n == 3:
        return -1
    if s == "0110":
        return 3
    return 2


t = int(input())
for _ in range(t):
    print(solve())