Nが非常に大きいこと、クエリ操作が必要なことから高度なデータ構造の問題のように思えるが、交換回数が非常に小さい事に着目すれば実際は尺取法であることに気付く。
M (5 ≤ M < 200000)
ai (1 ≤ ai ≤ 100)
文中の操作とまったく同じ操作を行えるデータ構造を用意すれば
O(M*ai)により余裕をもって間に合う。
またこのような操作を実現するデータ構造を双方向連結リストというらしい(別名Deque)

#include <iostream>
#include <algorithm>

using namespace std;

#define FOR(I,N) for(int I = 0; I < (int)(N); I++)
#define FIN(V) cout<<V<<endl
#define pb push_back
#define INF 1 << 30
#define SIZE 1000000

typedef pair<int, int> P;

int deque[SIZE];
int bi,ai;

void clearDeque(){
	fill_n(deque,SIZE,-1);
	bi = SIZE/3;
	ai = bi-1;
}

void addDeque(int value){
	ai++;
	deque[ai] = value;
}

void query1(){
	ai++;
	if(ai==SIZE)ai = 0;
	deque[ai] = deque[bi];
	deque[bi] = -1;
	bi++;
	if(bi==SIZE)bi = 0;
}

void query2(){
	bi--;
	if(bi==-1)bi = SIZE-1;
	deque[bi] = deque[ai];
	deque[ai] = -1;
	ai--;
	if(ai==-1)ai = SIZE-1;
}

bool flag[200001];

int main(){
	int i,j;
	int n,m,q,a;
	cin>>n>>m>>q;
	clearDeque();
	FOR(i,n){
		addDeque(i);
	}
	fill_n(flag,200001,1);
	FOR(i,m){
		cin>>a;
		FOR(j,a){
			if(a%2==0)query1();
			else query2();
		}
		///cout<<deque[bi]<<endl;
		flag[deque[bi]] = 0;
		deque[bi] = -1;
		bi++;
	}
	FOR(i,q){
		cin>>a;
		cout<<flag[a]<<endl;
	}
	return 0;
}

単純に配列を使ってこのデータ構造を実現しようとすると、操作回数はM*ai=20000000にも及ぶのでメモリオーバーを起こしてしまう。
なので、先頭が-1(index)に到達したら

ai--;
if(ai==-1)ai = SIZE-1;

このように先頭を配列の一番後ろに飛ばしてしまうとよい。

2015-02-11

SRM649

レート 0→1300

明日JOIの参加記を書く予定

2015-02-06

JOI2014本選「フクロモモンガ」

AOJ0601

ダイクストラ法なのですが、コストの持ち方を工夫する必要があります。

memo[N] = 累計コスト+(木の高さ-現在位置)

このように持つと、正しくダイクストラ法により解を求めることが出来ます。

木の上下移動は最小限に抑える必要がありますが、木の距離から上下移動が必要かは簡単に調べることが出来るので、pushする前に上下移動が必要かどうかをその都度計算により調べます。

#include <bits/stdc++.h>
  
using namespace std;
  
#define ll long long
#define FOR(I,N) for(int I = 0;I<(int)(N);I++)
#define P pair<ll,ll>
#define pb push_back
#define INF 9223372036854775807
  
struct Node{
    vector<P> edges;
    int at;
    ll height;
    Node(int at_,ll height_){
        at = at_;
        height = height_;
    }
    Node(){}
};
  
vector<Node> ns;
  
int main(){
    int i,j;
    ll n,m,x,h,a,b,c;
    cin>>n>>m>>x;
    FOR(i,n){
        cin>>h;
        ns.pb(Node(i,h));
    }
    FOR(i,m){
        cin>>a>>b>>c;a--;b--;
        ns[a].edges.pb(P(b,c));
        ns[b].edges.pb(P(a,c));
    }
  
    ll memo[100001];
    fill_n(memo,100001,INF);
    priority_queue<P> que;
    vector<P> alp;
    alp.pb(P(0,x));
    que.push(P(-(ns[0].height-x),alp.size()-1));
    ll ans = INF;
    while(que.size()){
        P data = que.top();que.pop();
        P data2 = alp[data.second];
        ll cost = -data.first;
        int index = data2.first;
        ll tx = data2.second;
        if(memo[index]<=cost)continue;
        memo[index] = cost;
        if(index==n-1){
            ll tcost = cost-(ns[index].height-tx);
            ans = min(ans,tcost+ns[index].height-tx);
            ///break;
        }
  
        FOR(i,ns[index].edges.size()){
            int nind = ns[index].edges[i].first;
            ll distance = ns[index].edges[i].second;
            ll tcost = cost-(ns[index].height-tx);///本来のコスト
            ll ncost;
            ll nx;
            if(tx-distance<0){///移動後の位置がマイナスになる
                if(ns[index].height<tx+distance-tx)///高さ足りない
                    continue;
                ncost = tcost+distance-tx+distance+ns[nind].height-0;
                nx = 0;
            }else if(ns[nind].height<tx-distance){///移動後の位置が木の高さ超える
                ncost = tcost+(tx-distance)-ns[nind].height+distance+0;
                nx = ns[nind].height;
            }else{
                ncost = tcost+distance+ns[nind].height-(tx-distance);
                nx = tx-distance;
            }
            alp.pb(P(nind,nx));
            que.push(P(-ncost,alp.size()-1));
        }
    }
    if(ans==INF)ans=-1;
    cout<<ans<<endl;
    return 0;
}

2015-02-06

PCK2014予選「天体観測」

AOJに問題が登録されたので解いてみました。
AOJ0302

予め星の輝きをソートしておきます。
ある星Aを決めると、(Aの輝き)以上かつ(Aの輝き+d)に最も近い星までが星座を作る星になるので、
その様に選んだ時の長方形の面積Sの大きさは
S = (星座内で最も大きいX座標-最も小さいX座標)(最も大きいY座標-最も小さいY座標)
となり、これを高速に求めるためにRMQを用います。
全ての星に対してこの操作を行った時の最も大きい長方形の面積が解となります。

#include<bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define FOR(I,N) for(int I = 0;I<(int)(N);I++)
#define P pair<ll,ll>
#define pb push_back
#define INF 10000000000
 
vector<P> datas;
P sorted[200001];
ll sortedV[200001];
 
ll BSEG[1<<19][2];///x,y
ll MSEG[1<<19][2];///x,y
 
void updataB(int index,int t){
    if(index==0)return;
    int l = index*2,r = index*2+1;
    ll tmp = BSEG[index][t];
    if(BSEG[l][t]<BSEG[r][t]){
        BSEG[index][t] = BSEG[r][t];
    }else{
        BSEG[index][t] = BSEG[l][t];
    }
    if(BSEG[index][t]==tmp)return;
    updataB(index/2,t);
}
 
void updataM(int index,int t){
    if(index==0)return;
    int l = index*2,r = index*2+1;
    ll tmp = MSEG[index][t];
    if(MSEG[l][t]>MSEG[r][t]){
        MSEG[index][t] = MSEG[r][t];
    }else{
        MSEG[index][t] = MSEG[l][t];
    }
    if(MSEG[index][t]==tmp)return;
    updataM(index/2,t);
}
 
ll getMin(int a,int b,int k,int l,int r,int t){
    if(b<l||r<a)return INF;
    if(a<=l&&r<=b)return MSEG[k][t];
    ll lm = getMin(a,b,k*2,l,(r-l)/2+l,t);
    ll rm = getMin(a,b,k*2+1,(r-l)/2+l+1,r,t);
    return min(lm,rm);
}
 
ll getMax(int a,int b,int k,int l,int r,int t){
    if(b<l||r<a)return 0;
    if(a<=l&&r<=b)return BSEG[k][t];
    ll lm = getMax(a,b,k*2,l,(r-l)/2+l,t);
    ll rm = getMax(a,b,k*2+1,(r-l)/2+l+1,r,t);
    return max(lm,rm);
}
 
int main(){
    int i,j;
    ll n,d,x,y,c;
    cin>>n>>d;
    FOR(i,n){
        cin>>x>>y>>c;
        P data = P(x,y);
        datas.pb(data);
        sorted[i] = P(c,datas.size()-1);
        sortedV[i] = c;
    }
    sort(sorted,sorted+n);
    sort(sortedV,sortedV+n);
    int index = 1;
    while(index<n)index*=2;
    fill_n(*BSEG,(1<<19)*2,0);
    fill_n(*MSEG,(1<<19)*2,INF);
    FOR(i,n){
        P data = datas[sorted[i].second];
        x = data.first;
        y = data.second;
        BSEG[index+i][0] = x;
        MSEG[index+i][0] = x;
        BSEG[index+i][1] = y;
        MSEG[index+i][1] = y;
        updataB((index+i)/2,0);
        updataB((index+i)/2,1);
        updataM((index+i)/2,0);
        updataM((index+i)/2,1);
    }
    ll ans = 0;
    FOR(i,n){
        ll source = sorted[i].first;
        ll r = source+d;
        int li = i;
        int ri = upper_bound(sortedV,sortedV+n,r)-sortedV-1;
        if(li==ri)continue;
        ll sum = (getMax(li,ri,1,0,index-1,0)-getMin(li,ri,1,0,index-1,0))
        *(getMax(li,ri,1,0,index-1,1)-getMin(li,ri,1,0,index-1,1));
        ans = max(ans,sum);
    }
    cout<<ans<<endl;
     
    return 0;
}

2015-02-06

セグメントツリーメモ

更新は再帰的に処理します。各操作O(logN)

///RMQ
#define SIZE (1<<18)
#define ll long long
#define INF (1<<30)///必要に応じて増やす

ll int MSEG[SIZE];

void update(int index){
	if(index==0)return;
	int l = index*2,r = index*2+1,tmp = MSEG[index];
	if(MSEG[l]<MSEG[r]){
		MSEG[index] = MSEG[l];
	}else{
		MSEG[index] = MSEG[r];
	}
	if(tmp==MSEG[index])return;///更新が無ければ終了
	update(index/2);
}

ll getMin(int a,int b,int k,int l,int r){
	if(b<l||a>r)return INF;///含まない
	if(a<=l&&r<=b)return MSEG[k];///[a,b]が[l,r]を完全に含む
	ll ml = getMin(a,b,k*2,l,(r-l)/2+l);///左側
	ll mr = getMin(a,b,k*2+1,(r-l)/2+l+1,r);///右側
	return min(ml,mr);
}

hokekyo1210メモ

PCK2014予選「バトンリレーゲーム」

SRM649

JOI2014本選「フクロモモンガ」

PCK2014予選「天体観測」

セグメントツリーメモ