BAPC 2017 J - Jumping Choreography
問題
問題概要
はじめ、数直線上に匹のカエルがいる。番目のカエルの位置はである。
カエルはジャンプによって移動することができる。1回のジャンプでは、カエルは左か右に跳ぶことができる。しかし、その移動距離は、1回目のジャンプでは距離1、2回目のジャンプでは距離2、3回目のジャンプでは距離3、...、とジャンプ回数を重ねるごとに1ずつ増加していく。
カエルたちは、座標に集まりたいので、集まるために必要なジャンプ回数の和の最小値を求めてほしい。
次のようなクエリが合計で個与えられる:
- addクエリ : カエルを位置に1匹追加する
- removeクエリ : カエルを位置から1匹除外する
- moveクエリ : 集合位置をに変更する
このような変更指示が順番に与えられるので、そこまでのクエリを反映したときの集まるために必要なジャンプ回数の和の最小値を答えよ。
- add,removeクエリは合わせて5000個以下
アイデア
まず、移動幅が1,2,3,...と増えていくことに注目すると、全部同じ方向に振った時、その移動距離の和は2乗ぐらいになるので、今回のフィールドの幅を移動するのに、必要な移動の回数は、だいたいルートをとってくらいにおさまっていると考えられる(実際に計算してみると1415回が最大)。
なので、まずは幅を移動するのに必要な最小のジャンプ回数(とする)を求めたい。注目すると、回数が2回増えるごとに、移動距離の合計の偶奇が入れ替わるので、全体に対しては言えないが、の偶奇で分類すると、それぞれのは非減少な列になる(つまり、であり、である)。
これは、である時(幅の移動は回で実現可能な時)、幅の移動がからまでを過不足なく使って、(足すグループ) - (引くグループ) = x
のような形で実現されていることを考え、便宜上が引くグループの方に入っていると見なせば、が引くグループに入っていて、が足すグループに入っているというのが成り立つが必ず存在することが言えるからである。もしこのようなが仮に無かったとすると、0は必ず引くグループに属していることから、全部が引くグループに属してないといけないことになり、その和は明らかに負になって矛盾するからである。そうすると、幅の移動はとのグループを交換することで回で実現することが言えて、この不等号が成り立つことが言えた。
ここからは、クエリに答えることを考える。集合場所をにしたときの答えを持つBITを考える。の偶奇によって、2種類のBITで管理することにする。そうすると、カエルが1匹増える時、このBITに加算される値というのは、...44443333222222110112223333...
みたいな形になっていると考えられる。同じ値の区間は、まとめて加算処理できることを考えると、上の考察も合わせて、区間は3000個以内に抑えられることが考えられる。制約から、addやremoveはそんなに多くないと言われているので、この新しいカエルが来るごとに、このの処理を行っても間に合うと考えられる。また、moveクエリは、BITがまさに答えを保持しているので、その部分を参照すれば良いので、で答えられる。
実装(C++)
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second using pi = pair<int,int>; struct BIT{ // [1,n] int n; vector<ll> bit; // 初期化 BIT(){} BIT(int _n){ n = _n; bit = vector<ll>(n+1,0); } // sum of [1,i] ll sum(int i){ ll s = 0; while(i>0){ s += bit[i]; i -= i & -i; } return s; } // add x in i-th element void add(int i, ll x){ while(i<=n){ bit[i] += x; i += i & -i; } } // [l,r] void add(int l, int r, ll x){ // printf("ADD %d %d %lld\n",l,r,x); l = (l+1)/2; r = (r+1)/2; add(l+1,x); add(r+2,-x); } }; BIT b[2]; vector<pi> e,o; const int P = 1100010; void init(){ e.pb({0,0}); int now = 0; for(int i=1; i<1500; ++i){ now += i; if(now>=P) break; if(now%2==1) o.pb({now,i}); else e.pb({now,i}); } rep(i,2) b[i] = BIT(P); } void FROG(int p, int m){ // printf(" F %d %d\n",p,m); int idx = (p+1)/2; int l = p, r = p; for(const auto &w:e){ int a = w.se; int nl = max(0,p-w.fi), nr = min(P-1,p+w.fi); b[p%2].add(nl,l,m*a); b[p%2].add(r,nr,m*a); l = max(0,nl-2); r = min(P-1,nr+2); } l = p-1; r = p+1; for(const auto &w:o){ int a = w.se; int nl = max(0,p-w.fi), nr = min(P-1,p+w.fi); b[!(p%2)].add(nl,l,m*a); b[!(p%2)].add(r,nr,m*a); l = max(0,nl-2); r = min(P-1,nr+2); } } ll ANS(int p){ return b[p%2].sum((p+1)/2 +1); } int main(){ init(); int n,t; scanf(" %d %d", &n, &t); ++t; rep(i,n){ int p; scanf(" %d", &p); ++p; FROG(p,1); } int C; scanf(" %d", &C); rep(_,C){ char q; int a; scanf(" %c %d", &q, &a); ++a; if(q=='t'){ t = a; } else{ int m = 1; if(q=='-') m = -1; FROG(a,m); } printf("%lld\n", ANS(t)); } return 0; }