No.290 1010

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 173
作問者 : antaanta

11 ProblemId : 335 / 出題時の順位表

問題文

0と1のみで構成される長さ$N$の文字列$S$が与えられる。 $S[a,b]$によって$S$の$a$文字目から$b$文字目まで(両端も含める)を繋げた部分文字列を表すとする。
$1 \le i \le j$かつ${j+(j+1-i)} \le N$を満たす2つの整数$i, j$に対して、$S[i,j] = S[{j+1},{j+(j+1-i)}]$となるようなものが存在するか?

入力

N
S

1行目に、整数$N (1 \le N \le 10^6)$が与えられる。 2行目に、0と1のみで構成される長さ$N$の文字列$S$が与えられる。

出力

問題文の条件を満たす整数の組が存在する場合には"YES"、存在しない場合には"NO"を1行に出力せよ(引用符は含めない)。

サンプル

サンプル1
入力
1
0
出力
NO
サンプル2
入力
2
00
出力
YES

$(i, j) = (1, 1)$が問題文の条件を満たします。

サンプル3
入力
14
00110101101010
出力
YES

たとえば、$S[3,7] = S[8,12] = 11010$なので$(i, j) = (3, 7)$などが条件を満たします。

提出ページヘ