裏紙

ほぼ競プロ、たまに日記

BAPC 2017 J - Jumping Choreography

問題

http://codeforces.com/gym/101666/attachments/download/6490/2017-benelux-algorithm-programming-contest-bapc-17-en.pdf

問題概要

はじめ、数直線上にn匹のカエルがいる。i番目のカエルの位置はp_iである。

カエルはジャンプによって移動することができる。1回のジャンプでは、カエルは左か右に跳ぶことができる。しかし、その移動距離は、1回目のジャンプでは距離1、2回目のジャンプでは距離2、3回目のジャンプでは距離3、...、とジャンプ回数を重ねるごとに1ずつ増加していく。

カエルたちは、座標tに集まりたいので、集まるために必要なジャンプ回数の和の最小値を求めてほしい。

次のようなクエリが合計でC個与えられる:

  • addクエリ : カエルを位置aに1匹追加する
  • removeクエリ : カエルを位置aから1匹除外する
  • moveクエリ : 集合位置をaに変更する

このような変更指示が順番に与えられるので、そこまでのクエリを反映したときの集まるために必要なジャンプ回数の和の最小値を答えよ。

  •  0 \le n \le 5000
  •  0 \le p_i \le 10^6
  •  0 \le t \le 10^6
  •  0 \le C \le 10^6
  •  0 \le a \le 10^6
  • add,removeクエリは合わせて5000個以下

イデア

まず、移動幅が1,2,3,...と増えていくことに注目すると、全部同じ方向に振った時、その移動距離の和は2乗ぐらいになるので、今回のフィールドの幅10^6を移動するのに、必要な移動の回数は、だいたいルートをとって10^3くらいにおさまっていると考えられる(実際に計算してみると1415回が最大)。

なので、まずは幅iを移動するのに必要な最小のジャンプ回数(dp_iとする)を求めたい。注目すると、回数が2回増えるごとに、移動距離の合計の偶奇が入れ替わるので、全体に対しては言えないが、iの偶奇で分類すると、それぞれのdp_iは非減少な列になる(つまり、dp_1 \le dp_3 \le dp_5 \le \ldotsであり、dp_2 \le dp_4 \le dp_6 \le \ldotsである)。

これは、dp_x = yである時(幅xの移動はy回で実現可能な時)、幅xの移動が1からyまでを過不足なく使って、(足すグループ) - (引くグループ) = xのような形で実現されていることを考え、便宜上0が引くグループの方に入っていると見なせば、zが引くグループに入っていて、z+1が足すグループに入っているというのが成り立つzが必ず存在することが言えるからである。もしこのようなzが仮に無かったとすると、0は必ず引くグループに属していることから、全部が引くグループに属してないといけないことになり、その和は明らかに負になって矛盾するからである。そうすると、幅x-2の移動はzz+1のグループを交換することでy回で実現することが言えて、この不等号が成り立つことが言えた。

ここからは、クエリに答えることを考える。集合場所をiにしたときの答えを持つBITを考える。iの偶奇によって、2種類のBITで管理することにする。そうすると、カエルが1匹増える時、このBITに加算される値というのは、...44443333222222110112223333...みたいな形になっていると考えられる。同じ値の区間は、まとめて加算処理できることを考えると、上の考察も合わせて、区間は3000個以内に抑えられることが考えられる。制約から、addやremoveはそんなに多くないと言われているので、この新しいカエルが来るごとに、この3000*O(logP)の処理を行っても間に合うと考えられる。また、moveクエリは、BITがまさに答えを保持しているので、その部分を参照すれば良いので、O(logP)で答えられる。

実装(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;
}