D - Flip to Gather Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

長さ N の 0 と 1 のみからなる文字列 S が与えられます。

あなたは以下の操作を何回でも( 0 回でもよい)行うことができます。

  • 1 \leq i \leq N を満たす整数 i を選び、S_i が 0 のときは 1 に、1 のときは 0 に変更する。

あなたの目標は S に含まれる 1 が高々 1 個の区間をなすようにすることです。目標を達成するために必要な操作回数の最小値を求めてください。

より厳密には以下の条件をともに満たすような整数の組 (l,r) が存在するような S にすることが目標です。目標を達成するために必要な操作回数の最小値を求めてください。

  • 1 \leq l \leq r \leq N+1
  • 1 \leq i \leq N を満たす整数 i に対し、S_i= 1 と l \leq i < r は同値である。

なお、有限回の操作で必ず目標が達成できることが証明できます。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

  • 1 \leq T \leq 20000
  • 1 \leq N \leq 2 \times 10^5
  • S は 0 と 1 のみからなる長さ N の文字列
  • 各入力ファイルについて、すべてのテストケースの N の総和は 2 \times 10^5 以下である。
  • T,N は整数

入力

入力は以下の形式で標準入力から与えられる。

T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T

\textrm{case}_i は i 番目のテストケースを表し、以下の形式で与えられる。

N
S

出力

T 行出力せよ。i 行目 (1 \leq i \leq T) には i 番目のテストケースに対する答えを出力せよ。

入力例 1

3
5
10011
10
1111111111
7
0000000

出力例 1

1
0
0

1 番目のテストケースにおいて、S_1 を 0 に変更する操作を行なうと、1 が 1 個の区間をなすようになります。また、S のままでは条件を満たしていません。したがって、答えは 1 です。

2 番目のテストケースにおいて、S に 0 が 1 個もないので、操作を行う必要はありません。したがって答えは 0 です。

3 番目のテストケースにおいて、S に 1 が 1 個もないので、操作を行う必要はありません。したがって答えは 0 です。

入力例 2

5
2
01
10
1000010011
12
111100010011
3
111
8
00010101

出力例 2

0
2
3
0
2

Score : 400 points

Problem Statement

You are given a string S of length N consisting of 0 and 1.

You can perform the following operation any number of times (possibly zero):

  • Choose an integer i satisfying 1 \leq i \leq N, and change S_i from 0 to 1, or from 1 to 0.

Your goal is to make the 1s in S form at most one interval. Find the minimum number of operations required to achieve the goal.

More precisely, the goal is to make S such that there exists a pair of integers (l,r) satisfying both of the following conditions. Find the minimum number of operations required to achieve the goal.

  • 1 \leq l \leq r \leq N+1.
  • S_i= 1 and l \leq i < r are equivalent for each integer i satisfying 1 \leq i \leq N.

It can be proved that the goal can always be achieved with a finite number of operations.

T test cases are given, so solve each.

Constraints

  • 1 \leq T \leq 20000
  • 1 \leq N \leq 2 \times 10^5
  • S is a string of length N consisting of 0 and 1.
  • For each input file, the sum of N over all test cases is at most 2 \times 10^5.
  • T,N are integers.

Input

The input is given from Standard Input in the following format:

T
\textrm{case}_1
\textrm{case}_2
\vdots
\textrm{case}_T

\textrm{case}_i represents the i-th test case and is given in the following format:

N
S

Output

Output T lines. The i-th line (1 \leq i \leq T) should contain the answer for the i-th test case.

Sample Input 1

3
5
10011
10
1111111111
7
0000000

Sample Output 1

1
0
0

In the first test case, if we perform the operation to change S_1 to 0, the 1s will form one interval. Also, the initial S does not satisfy the condition. Therefore, the answer is 1.

In the second test case, there are no 0s in S, so no operations need to be performed. Therefore, the answer is 0.

In the third test case, there are no 1s in S, so no operations need to be performed. Therefore, the answer is 0.

Sample Input 2

5
2
01
10
1000010011
12
111100010011
3
111
8
00010101

Sample Output 2

0
2
3
0
2