AtCoder AGC010 B - Boxes

解法

N=1のときは明らかにYES

以下、N>=2とする。

1回の操作で合計

b=1+2+...+N = N*(N+1)/2

足される。なので

Σ(A[i])がbで割り切れないときはNOとする。

操作回数をtとすると

t = Σ(A[i])/b

ここで数列cを以下のように定める

c[i] = b[(i+1) mod n] - b[i] (0<=i<=n-1)

仮にN=5として

a[i]に

-3, -4, -5, -1, -2

の操作をしたとすると

c[i]の増減は

-1, -1, +4, -1, -1

となる。

一般化してc[i]の増減は

-1, -1, ..., +(N-1), ...,-1, -1

のように表せる。

このc[i]の増減を分解すると

-1, -1, ..., -1, -1 (①)

0, 0, ..., +N, ..., 0, 0 (②)

(②の操作は任意の1箇所で＋N)

このように

①の操作と②の操作を別々にすると簡単。

数列cに①の操作をt回すると

d[i] = c[i] - t

が得られる。

あとは②の操作をdに対してt回適用して

すべて0にできればYES

まとめなど

必要条件を詰めていって、それが十分条件であることが直感的にわかればいい。階差数列の増減が単純。1回の操作を分解する。