No.406 鴨等間隔の法則

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 270
作問者 : はむ吉🐹はむ吉🐹 / テスター : btkbtk

2 ProblemId : 1221 / 出題時の順位表

問題文

太郎君は、家の近くにある河川敷で、$N (\ge 3)$羽の鴨が休んでいるのを見つけました。この河川敷はまっすぐです。そこで、上流のある地点を原点$x = 0$として、それぞれの鴨の休んでいる位置を$x$軸の$x\ge 0$を満たす部分にある点として表すことにします。そして、この$N$羽の鴨について、次の二つの条件が同時に成り立つときに限り、鴨等間隔の法則を満たしているということにします。

  1. どの2羽の鴨の座標も相異なる。
  2. 隣り合う2羽の鴨の座標の差がすべて等しい。
太郎君は、鴨の数$N$と鴨の休んでいる座標$x_0, x_1, \cdots, x_{N-1}$を記録しました。これらが与えられるので、$N$羽の鴨が鴨等間隔の法則を満たしているどうかを判定してください。

入力

$N$
$x_0$ $x_1$ $\cdots$ $x_{N - 1}$

1行目には、太郎君の見つけた鴨の数$N\:(3 \le N \le 10 ^ 5$)が正整数で与えられる。
2行目には、鴨$i (0 \le i \le N - 1)$の休んでいる座標$x_i\:(0 \le x_i \le 10 ^ 8)$が非負整数で、スペースで区切られて与えられる。ここで、「$j \lt k$ならば$x_j \lt x_k$である」とは限らない。

出力

$N$羽の鴨が鴨等間隔の法則を満たしていれば文字列YESを、さもなければ文字列NOを出力してください。最後に改行してください。

サンプル

サンプル1
入力
3
12 0 6
出力
YES

どの2羽の鴨を選んでも、座標が異なっています。また、隣り合う2羽の鴨の座標の差は6 - 0と12 - 6であり、いずれも6です。よって、両条件が成立するので、鴨等間隔の法則が満たされています。

サンプル2
入力
5
63 17 99 34 51
出力
NO

隣り合う2羽の鴨の座標の差をとると34 - 17 = 17, 51 - 34 = 17, 63 - 51 = 12, 99 - 63 = 36となり、条件2に反します。よって、これらの鴨は鴨等間隔の法則を満たしません。

サンプル3
入力
10
1299709 1299709 1299709 1299709 1299709 1299709 1299709 1299709 1299709 1299709
出力
NO

条件1に反しています。この時点で鴨等間隔の法則が満たされないとわかります。座標は大きな値になることがあります。

提出ページヘ