D - LCP(prefix,suffix)
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1200 点
問題文
長さ N の非負整数からなる数列 l が与えられます。
以下の条件を満たすような長さ N の文字列 s が存在するかどうかを判定してください。なお、文字の種類数に制限はないものとします。
- 条件:1 以上 N 以下のそれぞれの整数 i について、s[1:i] と s[N-i+1:N] の最長共通接頭辞の長さは l_i である
注釈
-
s[i,j] (i \leq j) は文字列 s の i 文字目から j 文字目までの部分文字列を指します。 例えば、s=
ABCBC
のとき、s[2:4] はBCB
,s[4:5] はBC
となります。 -
文字列 s,t の共通する接頭辞のうち、最長のものを s,t の最長共通接頭辞と呼びます。 例えば s=
ABCBC
,t=ABD
のとき、最長共通接頭辞はAB
となり、s=ABC
,t=BCD
のとき最長共通接頭辞は空文字列となります。
制約
- 1 \leq N \leq 3 \times 10^{5}
- 0 \leq l_i \leq i
- 与えられる入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N l_1 l_2 ... l_N
出力
条件を満たすような長さ N の文字列 s が存在するならば Yes
を、そうでなければ No
を出力せよ。
入力例 1
3 1 0 3
出力例 1
Yes
- 例えば
aba
という文字列が条件を満たします。
入力例 2
2 1 0
出力例 2
No
- 長さ 2 の文字列は
aa
のような同じ文字の繰り返しで表せる文字列と、ab
のような異なる 2 つの文字からなる文字列がありますが、どちらも条件を満たしません。
入力例 3
29 1 0 3 1 1 1 0 6 1 1 1 0 6 1 1 1 0 6 1 1 1 0 6 1 1 1 1 0 29
出力例 3
Yes
入力例 4
18 1 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 17 18
出力例 4
No