Mister雑記

競プロやります。

AGC010-B 「Boxes」 (500)

beta.atcoder.jp

概要

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

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

  1. 箱を1つ選ぶ( i番目の箱を選んだとする)。
  2.  1 \leq j \leq 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個取り除かれることから、 \{A_i\}の総和をこれで割った値となる。そもそも割り切れない場合は当然不可能となる。以降この合計操作回数を 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になっていないといけないので、

 \displaystyle M - Nx = d_i \Leftrightarrow x = \dfrac{M - d_i}{N}

が成立する。これで箱 iの選ばれる回数が求まった。

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

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

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

実装例

#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;
}

感想

  • 初見時はかなり苦戦したが、今ならコンテスト中に解ける気がする。
  • 解いてるときは判定でこんがらがっていたが、記事書いたらスッキリした。
    •  iを選ぶ回数を xとおいたのが肝っぽい。