東工大勢はなんかBIT/SegTree/HL分解/平衡二分木などのデータ構造ゲーが好きなイメージがある。…１人か２人かもしれないが。
http://yukicoder.me/problems/662
問題
N本の竹が順に並んでおり、それぞれの長さはA[i]である。
幾つかの竹を取り除き、残された竹が門松列を構成するようにしたい。
竹の列が門松列を成すとは以下の状態を満たす場合を意味する。
- 3本以上の丈の列である。
- 連続する3本の丈の長さはいずれも異なり、中央が最長または最短である。
最大で竹何本の門松列を構成できるか。
解法
Editorialを見て回答。
最初にAは座標圧縮しておこう。
左から順に竹を残す/取り除くを決めていくDPを考える。
dp[L][M]を、DP中において右端２本の長さがL,Mである最大門松列長とする。
R=A[i]が右端になる場合を考えると、dp[M][R] = max(dp[L][M]+1) (ただしLはL!=Rかつ(L＜MかつM＞R)または(L＞MかつM＜R)を満たすもの)で状態を更新していけば良い。
ただ、このDPはこのまま処理するとO(N^3)かかる。
max内をRMQと見なせばO(N^2*logN)になるし、max(dp[L][M])は常に上位２位まで覚えておけばよい(どちらかのLはRと不一致だから)ことを考慮するとO(N^2)まで落とせるが、まだこれでも間に合わない。
ここで、max(dp[L][M])についてLを上位２位まで覚えておけばよいように、Mについても上位２位まで考慮すれば十分であることを用いる。
M番目の要素としてdp[L][M]の上位２位まで覚えさせ、区間に対してはLの異なるdp[L][M]の上位２位を求められるSegTreeを使いDPしていこう。
(dp[L][M]は実際は２次元配列ではなく、各Mに対しLを上位２個だけ覚えておけばよいので、メモリ容量はO(N))
直前２要素が降下している(L＞M)場合と上昇している(L＜M)場合の２つのSegTreeを用いる。
例えば前者を用いる場合、次はM＜Rでなければならない。
よって0≦M＜Rの範囲でSegTreeを検索し、dp[L][M]の最大値を求める。
また、0≦M'＜MおよびM＜M'＜Rの範囲で再度SegTreeを検索し、dp[L'][M']が２番手になるようなL',M'を求める。
上記２値M,M'に対し、dp[M][R]およびdp[M'][R]を更新していこう。
だいぶ大ざっぱに書いているので、Editorialを見た方が良いです。
typedef pair<int,pair<int,int>> entry; typedef pair<entry,entry> node; node comp(vector<entry> v,node def) { sort(ALL(v)); reverse(ALL(v)); for(int i=v.size()-1;i>=1;i--) if(v[i].second.first==v[i-1].second.first) v.erase(v.begin()+i); while(v.size()<2) v.push_back(def.first); return {v[0],v[1]}; } node comp(node n1,node n2,node def) { vector<entry> v; if(n1.first.first>0) v.push_back(n1.first); if(n1.second.first>0) v.push_back(n1.second); if(n2.first.first>0) v.push_back(n2.first); if(n2.second.first>0) v.push_back(n2.second); return comp(v,def); } template<class V,int NV> class SegTree_1 { public: vector<V> val; V def; void init(V def_){def=def_;val=vector<V>(NV*2,def);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { if(r<=x || y<=l || x>=y) return def; 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),def); } void update(int entry, V v) { entry += NV; val[entry]=comp(val[entry],v,def); while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1],def); } }; SegTree_1<node,1<<18> st_inc,st_dec; int N; int A[101010],rev[101010]; map<int,int> M; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i],M[A[i]]=0; x=0; FORR(r,M) r.second=++x,rev[x]=r.first; int ma=0; st_inc.init({{0,{0,x+1}},{0,{0,x+1}}}); st_dec.init({{0,{0,0}},{0,{0,0}}}); FOR(i,N) { A[i]=M[A[i]]; { // dec node hoge=st_dec.def, hoge2=st_dec.def; auto r=st_inc.getval(A[i]+1,N+2); int m=r.first.second.second; vector<entry> e,e2; e.push_back(r.first); e.push_back(r.second); e.push_back(st_inc.val[m+(1<<18)].second); r=comp(st_inc.getval(A[i]+1,m),st_inc.getval(m+1,N+2),st_inc.def); m=r.first.second.second; e.push_back(r.first); e.push_back(r.second); e.push_back(st_inc.val[m+(1<<18)].second); sort(ALL(e)); e.erase(unique(ALL(e)),e.end()); FORR(rr,e) if(A[i]!=rr.second.first) e2.push_back({rr.first+1,{rr.second.second,A[i]}}), ma=max(ma,rr.first+1); st_dec.update(A[i],comp(e2,st_dec.def)); } { // inc node hoge=st_inc.def, hoge2=st_inc.def; auto r=st_dec.getval(0,A[i]); int m=r.first.second.second; vector<entry> e,e2; e.push_back(r.first); e.push_back(r.second); e.push_back(st_dec.val[m+(1<<18)].second); r=comp(st_dec.getval(0,m),st_dec.getval(m+1,A[i]),st_dec.def); e.push_back(r.first); e.push_back(r.second); m=r.first.second.second; e.push_back(st_dec.val[m+(1<<18)].second); e.erase(unique(ALL(e)),e.end()); FORR(rr,e) if(A[i]!=rr.second.first) e2.push_back({rr.first+1,{rr.second.second,A[i]}}), ma=max(ma,rr.first+1); st_inc.update(A[i],comp(e2,st_inc.def)); } } if(ma<3) ma=0; cout<<ma<<endl; }
まとめ
直前に覚えた「竹を短くする魔法」で残せる竹が増えるかもしれないのに、忘れちゃったんですかね？
