kmjp's blog

競技プログラミング参加記です

Codeforces #437 D. Buy Low Sell High

Codeforces

余り自信がなかったがなんか通った。
http://codeforces.com/contest/866/problem/D

問題

N日の株価の遷移が与えられる。
初期状態で所持金が十分に多いが、株は１つも持っていないとする。
毎日、株は最大１個売買できるとき、N日後の利益を最大化せよ。

解法

２部マッチングっぽく解けそうだが、それだとO(N^2)かかりそう。

自分は以下のように解いた。
株価の低い順に、RMQを使って自身より後の日付のうちまだペアになっておらず最も株価の高い日を選びペアにしよう。
そのようなペアが作れれば低い日に買って高い日に売ると差額の分得をする。

ただしこの場合、[3,7,4,8]のような遷移のとき、(3,7),(4,8)とペアを組めば8の利益が出るのに、(3,8)と先にペアを作ってしまうと5しか利益が組めない。
これをバラして(3,7),(4,8)と組みなおせるケースを考える。
(3,8)のペアがある場合、その間には株を１個以上持っている状態である。
そのため、先に7で株を売って、4で買う、と日付と逆順に組み合わせてもよいことになる。

上記考えをコードに起こそう。
区間加算・区間最小値を求められるSegTreeを使い、株の保持数の最小値を求められるようにする。
最初の処理では株価の低い順に、あとの日付だけから株価の高い日を探していたが、株を１個以上持っている場合、前の日付にさかのぼって同様に高い株価とペアを組んでもよい。
格子で組んだペアを一旦バラすことで解が得られる。

template<class V,int NV> class SegTree_Pair {
public:
	vector<pair<V,int> > val;
	static V const def=0;
	pair<V,int> comp(pair<V,int> l,pair<V,int> r){ return max(l,r);}
	SegTree_Pair(){
		val.resize(NV*2);
		int i;
		FOR(i,NV) val[i+NV]=make_pair(def,i);
		for(i=NV-1;i>=1;i--) val[i]=comp(val[2*i],val[2*i+1]);
	};
	pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return make_pair(def,NV);
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=make_pair(v,entry-NV);
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

static ll const def=0;
template<class V,int NV> class SegTree_3 {
public:
	vector<V> val, ma;
	SegTree_3(){
		int i;
		val.resize(NV*2,0); ma.resize(NV*2,0);
		FOR(i,NV) val[i+NV]=ma[i+NV]=def;
		for(i=NV-1;i>=1;i--) ma[i]=min(ma[2*i],ma[2*i+1]);
	};
	
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return 1<<30;
		if(x<=l && r<=y) return ma[k];
		return val[k]+min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k]+=v;
			ma[k]+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=val[k]+min(ma[k*2],ma[k*2+1]);
		}
	}
};

SegTree_Pair<int,1<<22> stmax;
SegTree_3<int,1<<22> str;


int N;
int P[303030];
vector<pair<int,int>> V;
int did[303030];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i];
		V.push_back({P[i],i});
		stmax.update(i,P[i]);
	}
	sort(ALL(V));
	ll ret=0;
	FORR(v,V) {
		x=v.second;
		if(did[x]) continue;
		int L=x;
		for(i=20;i>=0;i--) {
			if(L-(1<<i)<0) continue;
			if(str.getval(L-(1<<i),x+1)>0) L-=1<<i;
		}
		auto cand=stmax.getval(x,N);
		if(L<x) cand=max(cand,stmax.getval(L,x));
		if(cand.first==0) continue;
		y=cand.second;
		if(P[y]<=P[x]) continue;

		ret+=P[y]-P[x];
		
		did[y]=did[x]=1;
		stmax.update(x,0);
		stmax.update(y,0);
		if(y<x) {
			str.update(y,x,-1);
		}
		else {
			str.update(x,y,1);
		}
	}
	cout<<ret<<endl;
	
}

まとめ

これ解けたのになんでBを落とすのか…。