これは本番解きたかったな…。
https://csacademy.com/contest/fii-code-2020-round-1/task/enchained/
問題
N個の鉄の輪があり、それぞれの左端L[i]と右端R[i]が与えられる。
鉄の太さは1である。
これらの輪のうち一部を選択し、連結して鎖を作りたい。
この時、元のN個の輪に、1個だけ任意の位置に直径Xの鉄の輪を追加できるとする。
最大で何個の輪からなる鎖を構築できるか。
解法
まず追加の鎖がないケースを考える。
以下を考えよう。実質輪を左から並べたときに右端2つ分の情報を持つ。
f(i) := i番目の輪を右端にする場合、その右に来る輪の左端の範囲が[x,L[i]-1]であるようなケースにおける(x, 輪数)の対を輪数昇順に並べた列
上記値の最大値を求めれば、追加の鎖がないケースが求められる。
同様に、左右反転した以下のケースを考える。
g(j) := i番目の輪を左端にする場合、その左に来る輪の右端の範囲が[R[i]+1,x]であるようなケースにおける(x, 輪数)の対を輪数昇順に並べた列
これらを用いて輪を追加するケースを考える。
f(i)において、仮に(x,y)という対があったとする。この時、左端が[max(x,L[i]-X),L[i]-1]であるように鎖を配置することで、あるg(j)の要素に含まれる鎖(x',y')と連結できるなら、y+y'+1が候補となる。
これは先に座標圧縮しておくと、Range Maximum Queryを解けるSegTreeがあれば、f(i)の値に対応して区間最大値を更新し、g(j)の値に対応して区間最大値を参照することで解ける。
template<class V,int NV> class SegTree_3 { public: vector<V> val,ma; SegTree_3(){ int i; val.resize(NV*2,0); ma.resize(NV*2,0); }; V getval(int x,int y,int l=0,int r=NV,int k=1) { if(r<=x || y<=l) return 0; if(x<=l && r<=y) return ma[k]; return max({val[k],getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1)}); } void update(int x,int y, V v,int l=0,int r=NV,int k=1) { if(l>=r) return; if(x<=l && r<=y) { val[k]=max(val[k],v); ma[k]=max(ma[k],val[k]); } else if(l < y && x < r) { update(x,y,v,l,(l+r)/2,k*2); update(x,y,v,(l+r)/2,r,k*2+1); ma[k]=max({val[k],ma[k*2],ma[k*2+1]}); } } }; SegTree_3<int,1<<21> st; int N,X; int L[2020],R[2020]; vector<pair<int,int>> Ldp[2020],Rdp[2020]; pair<int,int> LP[2020],RP[2020]; void solve() { int i,j,k,l,r,x,y; string s; vector<int> P; vector<pair<int,int>> ev; P.push_back(-1); P.push_back(2000000000); cin>>N>>X; FOR(i,N) { cin>>L[i]>>R[i]; LP[i]={L[i],i}; RP[i]={R[i],i}; ev.push_back({R[i],i+N}); ev.push_back({L[i],i}); } sort(LP,LP+N); sort(RP,RP+N); reverse(RP,RP+N); int ma=2; FOR(i,N) { j=LP[i].second; vector<pair<int,int>> cand; cand.push_back({L[j]+1,1}); FOR(x,N) if(L[x]<L[j]&&L[j]<R[x]&&R[x]<R[j]) { y=lower_bound(ALL(Ldp[x]),make_pair(L[j]+1,0))-Ldp[x].begin(); if(y) cand.push_back({R[x]+1,Ldp[x][y-1].second+1}); } sort(ALL(cand)); FORR(c,cand) { if(c.first<R[j]) { if(Ldp[j].size() && Ldp[j].back().first==c.first) Ldp[j].pop_back(); if(Ldp[j].empty() || Ldp[j].back().second<c.second) Ldp[j].push_back(c); ma=max(ma,c.second+1); } ma=max(ma,c.second); } FORR(c,Ldp[j]) P.push_back(max(R[j]+1,c.first+X-1)); P.push_back(R[j]+X-1); } FOR(i,N) { j=RP[i].second; vector<pair<int,int>> cand; cand.push_back({R[j]-1,1}); FOR(x,N) if(L[j]<L[x]&&L[x]<R[j]&&R[j]<R[x]) { y=lower_bound(ALL(Rdp[x]),make_pair(R[j],0))-Rdp[x].begin(); if(y<Rdp[x].size()) cand.push_back({L[x]-1,Rdp[x][y].second+1}); } sort(ALL(cand)); reverse(ALL(cand)); FORR(c,cand) { if(L[j]<c.first) { if(Rdp[j].size() && Rdp[j].back().first==c.first) Rdp[j].pop_back(); if(Rdp[j].empty() || Rdp[j].back().second<c.second) Rdp[j].push_back(c); ma=max(ma,c.second+1); } ma=max(ma,c.second); } FORR(c,Rdp[j]) P.push_back(min(c.first,L[j]-2+X)+1); P.push_back(L[j]+1); reverse(ALL(Rdp[j])); } sort(ALL(P)); P.erase(unique(ALL(P)),P.end()); sort(ALL(ev)); FORR(e,ev) { //FOR(i,P.size()-1) cout<<i<<":"<<P[i]<<":"<<P[i+1]<<"="<<st.getval(i,i+1)<<" "; //cout<<endl; if(e.second<N) { i=e.second; FORR(c,Rdp[i]) { x=lower_bound(ALL(P),L[i]+1)-P.begin(); y=lower_bound(ALL(P),min(c.first,L[i]-2+X)+1)-P.begin(); ma=max(ma,c.second+st.getval(x,y)); } } else { i=e.second-N; FORR(c,Ldp[i]) { x=lower_bound(ALL(P),max(R[i]+1,c.first+X-1))-P.begin(); y=lower_bound(ALL(P),R[i]+X-1)-P.begin(); st.update(x,y,c.second+1); } } } cout<<ma<<endl; }
まとめ
この期に及んでRMQのライブラリがバグってるのひどい。