B - Boxes

概要

$N$ 個の箱が環状に並んでいる。最初 $i$ 番目の箱には石が $A_i$ 個入っている。

ここから以下の操作を繰り返すことで、石を全ての箱から取り除くことが可能か判定せよ。

1. 箱を 1 つ選ぶ。 $i$ 番目の箱を選んだとする。
2. $j = 1, 2, \dots, N$ について、 $i + j$ 番目の箱から石を $j$ 個取り除く。
   • $k$ 番目の箱と $k + N$ 番目の箱は同一視する。
   • $i + j$ 番目の箱に石が $j$ 個入っていない場合、1 にて $i$ 番目の箱を選ぶことはできない。

制約

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$

解説

まず、合計の操作回数を求める。 1 回の操作で、石は合計 $N (N + 1) / 2$ 個取り除かれる。 したがって、 $\sum_{i=1}^N A_i$ を $N (N + 1) / 2$ で割った値が操作回数となる。割り切れない場合は不可能。 この操作回数を $M$ とおく。

次に、各箱を何回選んだのかを求める。これは、 $A_i$ と $A_{i + 1}$ の 差分 に注目すると求まる。

$d_i = A_{i + 1} - A_{i}$ と定める。この $d_i$ が各操作でどう変化するか考えると、以下の 2 パターンに分類できる。

1. $i$ 番目の箱を選んだ場合
   • $A_{i}$ は $N$ 、 $A_{i + 1}$ は $1$ 減少する。
   • よって $d_i$ は $N - 1$ 増加する。
2. $i'$ 番目 ($i' \neq i$) の箱を選んだ場合
   • $A_{i}$ は $i - i'$ 、 $A_{i + 1}$ は $i - i' + 1$ 減少する。
   • よって $d_i$ は $1$ 減少する。

以上より、 $M$ 回の操作のうち箱 $i$ を $x$ 回選んだとすると、 $d_i$ は $(M - x) - (N - 1) x = M - Nx$ だけ減少することになる。 $M$ 回の操作後に $d_i$ は $0$ になっていないといけないので、 $M - Nx = d_i$ が成り立つ。これを解けば $x$ が求まる。

$$ x = \dfrac{M - d_i}{N} $$

箱が選ばれる回数 $x$ は非負整数でなくてはならないため、

• $M - d_i$ が $N$ で割り切れない
• $M - d_i \lt 0$

のいずれかを満たす場合は即アウトとなる。 逆に全ての $i$ でこれが満たされていれば、操作回数 $x$ の合計は常に $M$ に一致する¹ ため OK となる。

実装例

提出 #4780166 - AtCoder Grand Contest 010

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <iostream>
using namespace std;
using ll = long long;

int main() {
    ll N;
    cin >> N;

    ll A[N], sum = 0;
    for (ll i = 0; i < N; ++i) {
        cin >> A[i];
        sum += A[i];
    }

    if (sum % (N * (N + 1) / 2) > 0) {
        cout << "NO" << endl;
        return 0;
    }

    // 合計操作回数
    ll M = sum / (N * (N + 1) / 2);

    for (ll i = 0; i < N; ++i) {
        ll d = A[(i + 1) % N] - A[i];

        // 箱iの選ばれる回数は(M-d)/Nとなる
        // この値は非負整数でなくてはならない
        if (M < d || (M - d) % N > 0) {
            cout << "NO" << endl;
            return 0;
        }
    }

    cout << "YES" << endl;
    return 0;
}