kmjp's blog

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

WUPC 2019 : I - Ramen

ライブラリの完成度が低くて苦戦。
https://atcoder.jp/contests/wupc2019/tasks/wupc2019_i

問題

通りにN個のラーメン屋ができる。
各ラーメン屋について、位置・開店日・閉店日・おいしさが与えられる。
各ラーメン屋のラーメンの値段は、開店日前日に回転している他のラーメン屋の影響を受け、

  • おいしさ
  • 開店日前日に回転しているラーメン屋のラーメンの値段+(距離の2乗)

の最小値と一致する。

各ラーメン屋のラーメンの値段を答えよ。

解法

後者の条件よりConvex Hull Trickが使えそうというのは想像がつく。
一方ラーメン屋に閉店日の設定があるので、直線の削除ができないConvex Hull Trickそのままでは扱いにくい。
そこで、日付をキーにし、値に動的Convex Hull Trickを行える構造を載せたSegTreeを作ろう。

ちなみに自分の動的Convex Hull Trickのライブラリはdoubleには使えても整数ではうまく動かなかったので、Li Chao Treeを実装した。

template<typename V> struct LeChaoTree {
	static const V inf=3LL<<60;
	const ll range=1<<20;
	const bool cmptype=false; //true:max false:min
	struct node {
		node(V a=0,V b=-inf) : A(a),B(b){ le=ri=NULL;}
		V val(ll x) { return A*x+B;}
		V A,B;  // Ax+B
		node *le, *ri;
	};
	
	node* root;
	LeChaoTree() { root=new node(0,-inf);}
	
	void add(node* n, V a,V b,ll L,ll R) {
		ll M=(L+R)/2;
		
		bool lef=(n->val(L) > a*L+b);
		bool mid=(n->val(M) > a*M+b);
		bool ri=(n->val(R) > a*R+b);
		
		if(lef&&ri) return;
		if(!lef&&(!ri || R-L==1)) {
			n->A=a;
			n->B=b;
			return;
		}
		
		if(R-L==1) return;
		if(!n->ri) n->ri=new node();
		if(!n->le) n->le=new node();
		add(n->ri,a,b,M,R);
		add(n->le,a,b,L,M);
	}
	
	void add(V a,V b) { 
		if(!cmptype) a=-a,b=-b;
		add(root,a,b,0,range);
	}
	
	V query(ll x) {
		V ret=-inf;
		node* cur=root;
		ll L=0, R=range;
		while(cur) {
			ret=max(ret,cur->val(x));
			ll m=(L+R)/2;
			if(x<m) cur=cur->le, R=m;
			else cur=cur->ri, L=m;
			
		}
		
		if(!cmptype) ret=-ret;
		return ret;
	}
};

template<class V,int NV> class SegTree_2 {
public:
	vector<V> val;
	SegTree_2(){
		val.resize(NV*2);
	};
	
	ll getval(int k,ll x) {
		int e=k+NV;
		ll ret=3LL<<60;
		while(e>=1) {
			ret=min(ret,val[e].query(x));
			e>>=1;
		}
		return ret;
	}
	
	void update(int x,int y, ll a,ll b,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k].add(a,b);
		}
		else if(l < y && x < r) {
			update(x,y,a,b,l,(l+r)/2,k*2);
			update(x,y,a,b,(l+r)/2,r,k*2+1);
		}
	}
};
SegTree_2<LeChaoTree<ll>,1<<17> st;

int N;
ll O[101010],C[101010],D[101010],X[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>O[i]>>C[i]>>D[i]>>X[i];
		if(C[i]==-1) C[i]=101000;
		X[i]=min(X[i],st.getval(O[i]-1,D[i])+D[i]*D[i]);
		st.update(O[i],C[i]+1,-2*D[i],X[i]+D[i]*D[i]);
		cout<<X[i]<<endl;
	}
	
	
}

まとめ

Convex Hull Treeのライブラリ、どうも自分で作ってるものの動作に自信がもてない…。