/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
正整数 N と、長さ N の 0 または 1 からなる数列 A=(A_1,A_2,\dots,A_N) が与えられます。
長さ N の英大文字のみからなる文字列 S であって、以下の操作を 0 回以上好きな回数行うことで A に 0 が含まれないようにできるものを 良い文字列 と呼びます。ここで、S_i (1\leq i\leq N) で S の i 文字目を表し、S_{N+1}=S_1,S_{N+2}=S_2,A_{N+1}=A_1 とします。
- 次のうちどちらかを選び、実行する。
- 1\leq i\leq N なる整数 i であって S_i=
A、S_{i+1}=R、S_{i+2}=Cとなるものを選び、A_i,A_{i+1} を 1 に置き換える。 - 1\leq i\leq N なる整数 i であって S_{i+2}=
A、S_{i+1}=R、S_i=Cとなるものを選び、A_i,A_{i+1} を 1 に置き換える。
- 1\leq i\leq N なる整数 i であって S_i=
良い文字列が存在するか判定してください。
制約
- 3\leq N\leq 200000
- A_i\in \lbrace 0,1 \rbrace (1\leq i\leq N)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
良い文字列が存在するならば Yes と、存在しないならば No と出力せよ。
正誤判定器は大文字と小文字を区別せず、どちらも受理する。例えば、答えが Yes となるときに yes や YES、yEs などと出力しても正解と判定される。
入力例 1
12 0 1 0 1 1 1 1 0 1 1 1 0
出力例 1
Yes
例えば RARCARCCRAGC は良い文字列です。以下のように操作することで、A の全ての要素を 1 にすることが可能であるからです。
- はじめ、A=(0,1,0,1,1,1,1,0,1,1,1,0) である。
- i=2 として前者の操作をする。A=(0,1,1,1,1,1,1,0,1,1,1,0) となる。
- i=5 として前者の操作をする。A=(0,1,1,1,1,1,1,0,1,1,1,0) となる。
- i=8 として後者の操作をする。A=(0,1,1,1,1,1,1,1,1,1,1,0) となる。
- i=12 として後者の操作をする。A=(1,1,1,1,1,1,1,1,1,1,1,1) となる。
良い文字列が存在するので、Yes と出力してください。
入力例 2
3 0 0 0
出力例 2
No
良い文字列は存在しません。
入力例 3
29 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
出力例 3
Yes
操作するまでもなく A に 0 は含まれていないので、英大文字からなる長さ 29 の文字列はすべて良い文字列です。
Score : 400 points
Problem Statement
You are given a positive integer N and a sequence A=(A_1,A_2,\dots,A_N) of length N, consisting of 0 and 1.
We call a string S of length N, consisting only of uppercase English letters, a good string if it is possible to perform the following operation any number of times (possibly zero) so that the sequence A contains no 0. Here, S_i (1\leq i\leq N) denotes the i-th character of S, and we define S_{N+1}=S_1, S_{N+2}=S_2, and A_{N+1}=A_1.
- Perform one of the following operations:
- Choose an integer i with 1\leq i\leq N such that S_i=
A, S_{i+1}=R, and S_{i+2}=C, and replace each of A_i and A_{i+1} with 1. - Choose an integer i with 1\leq i\leq N such that S_{i+2}=
A, S_{i+1}=R, and S_i=C, and replace each of A_i and A_{i+1} with 1.
- Choose an integer i with 1\leq i\leq N such that S_i=
Determine whether there exists a good string.
Constraints
- 3\leq N\leq 200000
- A_i\in \lbrace 0,1 \rbrace (1\leq i\leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
If there exists a good string, print Yes; otherwise, print No.
The judge is case-insensitive; for example, if the correct answer is Yes, outputs such as yes, YES, or yEs will also be accepted.
Sample Input 1
12 0 1 0 1 1 1 1 0 1 1 1 0
Sample Output 1
Yes
For example, RARCARCCRAGC is a good string. This is because it is possible to change all elements of A to 1 by performing the following operations:
- Initially, A=(0,1,0,1,1,1,1,0,1,1,1,0).
- Perform the first operation with i=2. Then, A=(0,1,1,1,1,1,1,0,1,1,1,0).
- Perform the first operation with i=5. Then, A=(0,1,1,1,1,1,1,0,1,1,1,0).
- Perform the second operation with i=8. Then, A=(0,1,1,1,1,1,1,1,1,1,1,0).
- Perform the second operation with i=12. Then, A=(1,1,1,1,1,1,1,1,1,1,1,1).
Since there exists a good string, output Yes.
Sample Input 2
3 0 0 0
Sample Output 2
No
Good strings do not exist.
Sample Input 3
29 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Sample Output 3
Yes
Since A already contains no 0, every string of length 29 consisting of uppercase English letters is a good string.