最初アプローチに迷ったけど、何とか一発正答。
http://arc026.contest.atcoder.jp/tasks/arc026_3
問題
長さLの廊下がある。
ここをN個の蛍光灯で照らしたい。
各蛍光灯は照らせる範囲(l[i],r[i])及び設置費用c[i]が決まっている。
廊下の全領域が最低1個以上の蛍光灯で照らされた状態にするのに、必要な最小費用を答えよ。
解法
廊下の座標0を左端、Lを右端とする。
一見マッチング問題に見えるので最小コストフローで解けそうだが、Lが大きいため単純なフローでは解けない。
ここで考え方を変え、蛍光灯をr[i]の昇順にソートし、照らす範囲の右端を伸ばすように考えてみる。
廊下の位置0~r[i]を全部照らすには、他の蛍光灯ですでにr[i]まで照らされているか、もしくは0からl[i]~(r[i]-1)までのいずれかまで照らされている状態で、(l[i],r[i])の蛍光灯を追加するかのいずれかである。
この場合の最小費用を求めるには、左端からl[i]~(r[i]-1)のいずれかまでを照らす場合の最小費用を求めなければいけない。
幸いこれはSegment Treeを使うとO(logL)で求められるので、全体でO(N*logL)で処理できる。
int N,L; int LL[100005],RR[100005],C[100005]; vector<int> P[100001]; set<int> S; ll cost[100002]; template<class V,int NV> class SegTree_1 { public: vector<V> val; static V const def=1LL<<60; V comp(V l,V r){ return min(l,r);}; SegTree_1(){val.resize(NV*2); clear();}; void clear() { int i; FOR(i,NV*2) val[i]=def;} V getval(int x,int y,int l,int r,int k) { if(r<=x || y<=l) 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)); } V getval(int x,int y) { return getval(x,y,0,NV,1);} void update(int entry, V v) { entry += NV; val[entry]=v; while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]); } }; void solve() { int f,i,j,k,l,x,y; cin>>N>>L; FOR(i,N) cin>>LL[i]>>RR[i]>>C[i]; FOR(i,N) P[RR[i]].push_back(i); SegTree_1<ll,1<<20> st; FOR(i,L+5) st.update(i,1LL<<60); st.update(0,0); FOR(i,L+1) { ll re=1LL<<60; ITR(it,P[i]) { x=*it; re=min(re,min(st.getval(i,i),st.getval(LL[x],i)+C[x])); } if(re<1LL<<60) st.update(i,re); } cout << st.getval(L,L+1) << endl; }
まとめ
フローの考えからSegTreeが思いつくまでちょっと時間がかかってしまった。