A - ARC Arc

Contest Duration: 2025-02-09(Sun) 12:00 - 2025-02-09(Sun) 14:00 (local time) (120 minutes) Back to Home

A - ARC Arc Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $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$ に置き換える。

良い文字列が存在するか判定してください。

制約

$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 などと出力しても正解と判定される。

入力例 1Copy

Copy

12
0 1 0 1 1 1 1 0 1 1 1 0

出力例 1Copy

Copy

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 と出力してください。

入力例 2Copy

Copy

3
0 0 0

出力例 2Copy

Copy

No

良い文字列は存在しません。

入力例 3Copy

Copy

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

出力例 3Copy

Copy

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$ .

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 1Copy

Copy

12
0 1 0 1 1 1 1 0 1 1 1 0

Sample Output 1Copy

Copy

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 2Copy

Copy

3
0 0 0

Sample Output 2Copy

Copy

No

Good strings do not exist.

Sample Input 3Copy

Copy

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 3Copy

Copy

Yes

Since $A$ already contains no $0$ , every string of length $29$ consisting of uppercase English letters is a good string.