Codeforces #185 Div1. B. Cats Transport

Bは知らないテクニックを使っていたので自分では解けなかった。
http://codeforces.com/contest/311/problem/B

問題

N個の丘が並んでおり、それぞれの距離が与えられる。
猫とトラックは速度１で丘の間を移動する。
M匹の猫が丘0からそれぞれ特定の丘に向け特定の時間に到着するよう出発する。

ここで、P台のトラックが丘0を出発して、すでに目的の丘にいる猫にエサをあげていく。
全部の猫にエサをあげる場合、猫が目的の丘についてからエサを得るまでの時間を最小化せよ。

解法

猫とトラックの速度は同じなので、猫が目的の丘についてからトラックが来るのを待つのと、猫が丘0で先にトラックの出発を待つのと待つ時間は同じである。
よって、目的の丘の位置と目的の時間から、丘0を出発する時間を求める。

ここまですると、この問題は以下のように書き換えられる。
各猫が丘0を出発する時間を並べた数列がある。
ここでP個数値を配置し、過去猫の出発時間の後にあるからもっとも近いP個の数値への時間の和を最小化するよう、P個を選ぶ。

まず、トラックはいずれかの猫の出発タイミングと会うタイミングで出る。
どの出発タイミングとも合わないと、差分の分待ち時間が増えるので意味がない。
律儀にM匹中P個のタイミングを選ぶDPを組むと、O(PM^2)かかってしまいTLEする。

そこで、Editorialにもあるconvex hull trick。
蟻本でも違う名前で載っている。これで途中で値を最大化する処理のオーダーを落とせる。

int N,M,P;
ll D[100001],H[100001],T[100001];
vector<ll> V;
vector<ll> S;
ll DP[101][100002];

ll f(int id,int x,int t){
	return DP[t][id-1] + S[x] - S[id]- (x-id)*V[id];
}

bool check(int id1,int id2,int id3,int t) {
	ll a1=-V[id1], b1=DP[t][id1-1] - S[id1] + V[id1]*(id1);
	ll a2=-V[id2], b2=DP[t][id2-1] - S[id2] + V[id2]*(id2);
	ll a3=-V[id3], b3=DP[t][id3-1] - S[id3] + V[id3]*(id3);
	return (a3-a1)*(b1-b2) >= (b1-b3)*(a2-a1);
}

void solve() {
	int r,i,j,k,l, x,y;
	
	cin>>N>>M>>P;
	
	FOR(i,N-1) D[i+1]=D[i]+GETi();
	FOR(i,M) {
		cin>>x>>y;
		V.push_back(y-D[x-1]);
	}
	sort(V.begin(),V.end());
	reverse(V.begin(),V.end());
	FOR(i,M) V[M-1-i] = V[0] - V[M-1-i];
	ll a=0;
	FOR(i,M) S.push_back(a+=V[i]);
	FOR(i,M) DP[0][i]=S[i];
	ll mi=DP[0][M-1];
	
	for(i=1;i<=P-1;i++) {
		deque<int> Q;
		
		for(x=1;x<=M-1;x++) {
			k=i-1;
			while(Q.size()>=2 && check(Q[Q.size()-2],Q[Q.size()-1],x,k)) Q.pop_back();
			Q.push_back(x);
			while(Q.size()>=2 && f(Q[0],x,k) >= f(Q[1],x,k)) Q.pop_front();
			DP[i][x] = f(Q[0],x,k);
		}
		mi=min(mi,DP[i][M-1]);
	}
	cout << mi << endl;
	return;
}

まとめ

convex hull trickを知らないと解けないけど、知ってたらどうにか解ける問題。
でもこれ、覚えられなさそう…。ライブラリ化もしにくいしなぁ。