Codeforces #219 Div1. C. Watching Fireworks is Fun

こちらも計算量に泣いたけど、そもそも理解していなかったアルゴリズムを使う必要があったのでしょうがない。
http://codeforces.com/contest/372/problem/C

問題

1～Nの町があり、それぞれ町番号に即した位置にある。

ここで花火大会が開催され、M回の花火が上がる。
各花火はA[i]の町でB[i]の強さで時刻T[i]に上がる。
自分が町xにいるとき、その満足度はB[i]-|A[i]-x|である。

自分は時間当たり速度Dで移動できるとき、満足度を最大化せよ。

解法

花火のうちB[i]分はどこにいても満足度として得られるので、先に合計してしまえばよい。
あとは|A[i]-x|の和を最小化するように移動する。

ここは花火を時刻順にソートし、自分の位置ごとにDPしていけばよい。
前の花火の段階での各位置における|A[i]-x|の最小値C[x]がわかっているとする。
前回と今回の時刻の差がdtなら、新たなC'[x]はC[x-dt*D]～C[x+dt*D]の間の最小値に、|A[i]-x|を足したものとなる。

ここで必要なのはC[x-dt*D]～C[x+dt*D]を高速に求めること。
自分は本番でSegTreeを用いたが、これは１回求めるのにlogNかかってしまったため全体でO(NMlogN)かかりTLEした。

そこで蟻本を見てスライド最小値方式を利用した。
１回の最小値計算がO(1)なので、全体がO(NM)で済む。
スライド最小値、本にあったのは知ってたけどSegTreeのまま突っ走っちゃったまま時間切れしちゃったよ。

ll N,M,D;
pair<ll,int> PP[500];

template<class V>
void slidemin(vector<V>& inin, vector<V>& ouout,int num) {
	deque<V> deq;
	int i;
	
	// this impl stor onlu N-(num-1) entries
	ouout.clear();
	FOR(i,inin.size()) {
		while(!deq.empty() && inin[deq.back()]>=inin[i]) deq.pop_back();
		deq.push_back(i);
		if(i>=num-1) ouout.push_back(inin[deq.front()]);
		if(!deq.empty() && deq.front()==i-num+1) deq.pop_front();
	}
}

void solve() {
	int f,i,j,k,l,x,y;
	ll tot=0,tt;
	
	cin>>N>>M>>D;
	FOR(i,M) {
		cin>>PP[i].second>>tt>>PP[i].first;
		PP[i].second--;
		tot+=tt;
	}
	sort(PP,PP+M);
	
	vector<ll> aa,bb,cc;
	FOR(i,N) aa.push_back(0);
	
	j=1;
	FOR(i,M) {
		x=(int)min((PP[i].first-j)*D,(ll)N-1);
		cc.clear();
		FOR(y,x) cc.push_back(1LL<<50);
		FOR(y,N) cc.push_back(aa[y]);
		FOR(y,x) cc.push_back(1LL<<50);
		
		slidemin<ll>(cc,bb,1+2*x);
		cc.resize(N);
		FOR(y,N) cc[y]=bb[y] + abs(PP[i].second-y);
		swap(aa,cc);
		j=PP[i].first;
	}
	sort(aa.begin(),aa.end());
	cout << tot-aa[0] << endl;
}

まとめ

今回これでスライド最小値を理解したつもり。
蟻本１度端から端までやり直そうかなぁ。