C - Seating Arrangement Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、文化祭の会場にある一列に並んだ N 個の座席の配置を担当しています。座席には左から順に番号 1 から N が振られています。

現在、いくつかの座席にはすでにお客さんが座っています。具体的には、座席 i の状態が S_i = 1 のとき人が座っており、S_i = 0 のとき空席です。

高橋君は、空いている座席のうちから 0 個以上好きなだけ選び、選んだ各座席に新たなお客さんを 1 人ずつ案内することができます。ただし、すでに座っているお客さんを移動させたり退席させたりすることはできません。また、各座席には最大 1 人しか座れません。さらに、会場の換気ルールにより、以下の条件を満たさなければなりません。

  • すべての案内が完了した後の座席の状態において、連続する 3 つの座席がすべて人が座っている状態である箇所が存在してはならない。

すなわち、すべての案内が完了した後の座席 i の状態を T_i（人が座っていれば 1、空席であれば 0）としたとき、1 \leq i \leq N-2 を満たすどの i についても T_i = T_{i+1} = T_{i+2} = 1 とはならないようにしなければなりません。なお、初期状態においてこの条件はすでに満たされていることが入力で保証されます。

高橋君は、この条件を満たしつつ、できるだけ多くのお客さんを新たに案内したいと思っています。新たに案内できるお客さんの最大人数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • S_i \in \{0, 1\}（1 \leq i \leq N）
  • 入力で与えられる初期状態において、連続する 3 つの座席がすべて人が座っている箇所は存在しない。すなわち、S_i = S_{i+1} = S_{i+2} = 1 となるような i（1 \leq i \leq N-2）は存在しない。
  • 入力はすべて整数である。

入力

N
S_1 S_2 \ldots S_N
  • 1 行目には、座席の数を表す整数 N が与えられる。
  • 2 行目には、各座席に人が座っているかを表す N 個の整数 S_1, S_2, \ldots, S_N がスペース区切りで与えられる。S_i = 1 のとき座席 i に人が座っており、S_i = 0 のとき空席である。

出力

条件を満たしつつ新たに案内できるお客さんの最大人数を 1 行で出力せよ。

入力例 1

5
0 0 1 0 0

出力例 1

2

入力例 2

7
1 0 0 0 0 0 1

出力例 2

3

入力例 3

15
0 0 0 1 0 0 0 0 1 1 0 0 0 0 0

出力例 3

7

入力例 4

30
0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0

出力例 4

12

入力例 5

1
0

出力例 5

1

Score : 366 pts

Problem Statement

Takahashi is in charge of arranging N seats lined up in a row at a cultural festival venue. The seats are numbered 1 through N from left to right.

Currently, some seats are already occupied by guests. Specifically, seat i is occupied if S_i = 1, and vacant if S_i = 0.

Takahashi can select 0 or more vacant seats as he likes and guide one new guest to each selected seat. However, he cannot move or remove guests who are already seated. Also, each seat can hold at most 1 person. Furthermore, due to the venue's ventilation rules, the following condition must be satisfied:

  • After all guests have been guided to their seats, there must be no three consecutive seats that are all occupied.

In other words, if we denote the state of seat i after all guidance is complete as T_i (1 if occupied, 0 if vacant), then for every i satisfying 1 \leq i \leq N-2, it must not be the case that T_i = T_{i+1} = T_{i+2} = 1. It is guaranteed in the input that the initial state already satisfies this condition.

Takahashi wants to guide as many new guests as possible while satisfying this condition. Find the maximum number of new guests that can be guided.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • S_i \in \{0, 1\} (1 \leq i \leq N)
  • In the initial state given in the input, there are no three consecutive seats that are all occupied. That is, there is no i (1 \leq i \leq N-2) such that S_i = S_{i+1} = S_{i+2} = 1.
  • All input values are integers.

Input

N
S_1 S_2 \ldots S_N
  • The first line contains an integer N representing the number of seats.
  • The second line contains N integers S_1, S_2, \ldots, S_N separated by spaces, representing whether each seat is occupied. S_i = 1 means seat i is occupied, and S_i = 0 means it is vacant.

Output

Print in one line the maximum number of new guests that can be guided while satisfying the condition.

Sample Input 1

5
0 0 1 0 0

Sample Output 1

2

Sample Input 2

7
1 0 0 0 0 0 1

Sample Output 2

3

Sample Input 3

15
0 0 0 1 0 0 0 0 1 1 0 0 0 0 0

Sample Output 3

7

Sample Input 4

30
0 1 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0

Sample Output 4

12

Sample Input 5

1
0

Sample Output 5

1