問題一覧 > 通常問題

No.1884 Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 152
作問者 : miscalcmiscalc / テスター : ShirotsumeShirotsume 👑 ygussanyygussany
4 ProblemId : 7845 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-03-24 10:37:49

問題文

$N$ 枚のカードが左右一列に並んでいます。各カードには、正の整数が $1$ つ書かれているか、あるいは何も書かれていません。左から $i$ 番目のカードの状態は非負整数 $A_i$ によって次のように表されます。

  • $A_i > 0$ のとき、左から $i$ 番目のカードには整数 $A_i$ が書かれている。
  • $A_i = 0$ のとき、左から $i$ 番目のカードには何も書かれていない。

ここで、カードに対して次の操作を行うことを考えます。

  • 何も書かれていないカードがあれば、それぞれに好きな正の整数を $1$ つずつ書き込む。その後、すべてのカードを好きな順番に並べ替える(そのままの順番でもよい)。

操作終了後に左から $i$ 番目にあるカードに書かれた整数を $B_i$ とするとき、数列 $B = (B_1, B_2, \ldots, B_N)$ が等差数列になるように操作を行うことは可能ですか? すなわち、$B_2 - B_1 = B_3 - B_2 = \cdots = B_N - B_{N - 1}$ が成り立つように操作を行うことは可能ですか?

入力

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

  • 入力はすべて整数である
  • $3 \leq N \leq 2 \times 10^5$
  • $0 \leq A_i \leq 10^{15}$

出力

$B$ が等差数列になるように操作を行うことが可能な場合は Yes、不可能な場合は No と出力してください。

サンプル

サンプル1
入力
5
0 7 3 0 9
出力
Yes

何も書かれていない $2$ 枚のカードにそれぞれ $1, 5$ を書き込んでカードを並べ替えると、$B = (1, 3, 5, 7, 9)$ とすることができます。

サンプル

サンプル2
入力
7
4 0 9 5 11 0 0
出力
No

サンプル

サンプル3
入力
4
1 1 0 1
出力
Yes

$B = (1, 1, 1, 1)$ とすることができます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。