一応手持ちのテクで解ける問題だった。
http://dwango2016-prelims.contest.atcoder.jp/tasks/dwango2016qual_e
問題
プレイヤーは座標0からLに向けて、非負の速度であれば任意のペースで移動できる。
途中N回花火が上がる。
時刻T[i]に位置P[i]で花火が上がるとき、プレイヤーが座標xにいると残念度が|P[i]-x|だけ上昇する。
最適な移動をしたとき、残念度の総和の最小値を求めよ。
解法
部分点解法
F(i,x)をi発目の花火が上がったとき、位置xにいる場合のi発目までの残念度の総和とする。
- T[i-1]==T[i]なら間に移動できないのでF(i,x) = F(i-1,x) + |P[i]-x|
- T[i-1]<T[i]なら間に正の向きに移動可能なのでF(i,x) = (min{0≦p≦x}F(i-1,p)) + |P[i]-x|
このDPはO(NL)で済むので、部分点はこれで間に合う。
満点解法
上記DPを何とか速くすることを考える。
その際、下記の記事の考察を参照した。ただし解法は別。
第2回 ドワンゴからの挑戦状 予選E 花火 のヒープ解法 - Qiita
F(i,x)は常に下に凸である。
よって、F(i,0)~F(i,L)において極小値となるxは最小値でもある。
以下のようなSegtreeを準備しよう。数を0にする処理は遅延処理可能なSegTreeで再現できる。
- xの範囲に対して同じ数を足す
- あるxに対し、現在の値を答える
- xの範囲に対し、数を0にする
位置P[i]で花火が上がるとき、位置xにいるプレイヤーの残念度は|P[i]-x|上昇する。
不等号を払うと、x未満の位置では-x+P[i]、x以降の位置ではx-P[i]上昇する。
そこでF(i,x)=a*x+bの形で表し、a及びbをそれぞれSegTreeで管理し、花火が上がる度にa,bを更新していく。
次に最小値を求める処理だが、これは上記のとおりF(i,x)が下に凸なので、三分探索で求めることができる。
三分探索でF(i,x)の最小値を求めたら、F(i,y)(y>x)についてa,bを一旦0にし、a=0,b=F(i,x)を足しこめば、F(i,y)をすべてF(i,x)と同じ値に出来る。
これでO(N*log^2L)とちょっと遅いが何とか間に合う。
三分探索を避け二分探索にするなど、もっと高速にする方法もあるようだ。
// 参照も更新もrange template<class V,int NV> class SegTree_3 { public: vector<V> val; vector<int> clean; SegTree_3(){ val.resize(NV*2); clean.resize(NV*2);} ll getval(int v,int l=0,int r=NV,int k=1) { if(r<=v || v<l) return 0; ll ret=val[k]; if(clean[k]==0 && r-l>=2) ret+=getval(v,l,(l+r)/2,k*2)+getval(v,(l+r)/2,r,k*2+1); return ret; } void add(int x,int y, V v,int l=0,int r=NV,int k=1) { if(l>=r || x>=y) return; if(x<=l && r<=y) { val[k]+=v; } else if(l < y && x < r) { if(clean[k]==1) { clean[k]=0; val[2*k]=val[2*k+1]=0; clean[2*k]=clean[2*k+1]=1; } add(x,y,v,l,(l+r)/2,k*2); add(x,y,v,(l+r)/2,r,k*2+1); } } void clear(int x,int y,int l=0,int r=NV,int k=1) { if(l>=r || x>=y) return; if(x<=l && r<=y) { val[k]=0; clean[k]=1; } else if(l < y && x < r) { if(clean[k]==1) { clean[k]=0; val[2*k]=val[2*k+1]=0; clean[2*k]=clean[2*k+1]=1; } val[2*k]+=val[k]; val[2*k+1]+=val[k]; val[k]=0; clear(x,y,l,(l+r)/2,k*2); clear(x,y,(l+r)/2,r,k*2+1); } } }; int N,L,M; vector<vector<int>> V; SegTree_3<ll,1<<17> bta,btb; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>L; j=0; FOR(i,N) { cin>>x>>y; if(x!=j) j=x,V.push_back(vector<int>()); V.back().push_back(y); } ll mix=0, miv=0; FORR(v,V) { FORR(r,v) { bta.add(0,r,-1); bta.add(r+1,L+1,1); btb.add(0,r,r); btb.add(r+1,L+1,-r); } int LL=0,RR=L; while(LL+6<=RR) { int x1=(LL*2+RR)/3; int x2=(LL+RR*2)/3; ll v1=bta.getval(x1)*x1+btb.getval(x1); ll v2=bta.getval(x2)*x2+btb.getval(x2); if(v1<=v2) RR=x2; else LL=x1; } miv=1LL<<60; for(x=LL;x<=RR;x++) { ll v=bta.getval(x)*x+btb.getval(x); if(v<miv) miv=v,mix=x; if(v>miv) break; } bta.clear(mix+1,L+1); btb.clear(mix+1,L+1); btb.add(mix+1,L+1,miv); } cout<<miv<<endl; }
解法
本番もう少し落ち着いて考えられたらな。