ゆるふわ競技プログラミングオンサイト at FORCIA #9
コンテスト日時
2026/11/07 (Sa) 14:15 - 16:45

C - Make Arithmetic Sequence

Benihuki
2
s
1024
MB
350
点

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。

次の操作をちょうど1回行います。

  • $1\leq L\leq R\leq N$ を満たす整数 $L,R$ と、整数 $X$ を選ぶ。$L\leq i\leq R$ を満たすすべての整数 $i$ に対して、$A_i$ に $X$ を加算する。

ここで、$X$ には0や負の整数を選んでも構いません。

操作後の $A$ を等差数列にすることができるか判定してください。
ただし、等差数列とは、隣り合う要素の差 $A_{i+1}-A_i$ がすべて等しい数列をいいます。公差が0や負の場合も含みます。

テストケースは $T$ 個与えられます。各テストケースについて答えを求めてください。

制約

  • $1\leq T\leq 10^5$
  • $2\leq N\leq 2\times 10^5$
  • $1\leq A_i\leq 10^9$($1\leq i\leq N$)
  • 全テストケースにおける $N$ の総和は $2\times 10^5$ 以下である。
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられます。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

各テストケースは以下の形式で与えられます。

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

出力

各テストケースについて、操作後の $A$ を等差数列にすることができる場合は Yes、できない場合は No を、入力された順に1行ずつ出力してください。

入力例 1
3 4 1 2 2 4 5 2 2 5 8 8 6 3292 72114 162831 253548 366160 456877
出力例 1
Yes No Yes

この入力には3個のテストケースが含まれます。

1個目のテストケースでは、$L=R=3, X=1$ として操作すると、$A=(1,2,3,4)$ となり、公差1の等差数列になります。

2個目のテストケースでは、どのように操作しても、$A$ を等差数列にすることはできません。

3個目のテストケースでは、$L=2, R=4, X=21895$ として操作すると、$A=(3292,94009,184726,275443,366160,456877)$ となり、公差90717の等差数列になります。

提出
C++23 (g++ 12.2.0)