kmjp's blog

競技プログラミング参加記です

AtCoder ARC #026 : C - 蛍光灯

最初アプローチに迷ったけど、何とか一発正答。
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が思いつくまでちょっと時間がかかってしまった。