AGC 010 B - Boxes

• 問題

問題概要

N個の数列{a_i} (1<=i<=N)に対して,
数字iを選び,全ての1<=j<=Nに対し, a_(i+j)%N を -jする
という操作を行う.

全てのaiを0にすることができるか.
1 <= N <= 10⁵, 1 <= a_i <= 10⁹

解法

1回の操作を行うと,合計は+N(N+1)/2されるので,合計をこれで割ると何回操作が行われるかがわかる.これをk回とする.
(N(N+1)/2で割って余りが出る場合はNOである)
ここで b_i = a_(i+1) - a_i に注目すると,1回の操作で1つが+(N-1)され,他が-1される(*)ことがわかる.
つまり,{b_i}に対してこの操作をk回繰り返して,全て0にできるか.という問題になる.

ここで,(*)の操作を以下のように分解すると,
1. 全て-1する
2. 一つ選び+Nする
操作はどの順番で行っても良い為,最初に全て-kしておき+Nをk回繰り返して0にできるか.という問題になる.
{b_i}の合計が0であることは b_i = a_(i+1) - a_iより明らかなので,
{b_i - k}が全てNの倍数で負であることが必要十分条件となる.

メモ

諸々エッセンスが詰まってそうな問題だった.
数列の操作が苦手なので押さえておきたい.
最初に考えること -> 操作は何回あるか?
連続して足していく -> 階差数列
数列の操作 -> 操作の分解,逆操作
この問題を思い出した.
こういう操作典型っぽい.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 100005;
int a[MAX_N];

int main(){
  ll N; cin >> N;
  ll ss = 0LL;
  rep(i,N){
    scanf("%d",a+i);
    ss += a[i];
  }
  bool ans = (ss%(N*(N+1)/2) == 0LL);
  ss /= (N*(N+1)/2);
  rep(i,N){
    ll b = (a[(i+1)%N] - a[i]);
    b -= ss;
    ans &= (b<=0LL && b%N==0LL);
  }
  if(ans) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}