CODE FESTIVAL 2015 決勝 : H - 焼肉の達人

Codeforcesに出そうな問題。
http://code-festival-2015-final-open.contest.atcoder.jp/tasks/codefestival_2015_final_h

問題

[0,M]の区間を覆う網で焼肉を焼く。
肉はN枚あり、各肉は網の上で[L[i],R[i]]の範囲を覆うように配置する。

焼肉をおいしく食べるには、網の上で一枚だけ肉が来るようにしなければならない。
任意の肉を取り除けるとき、1枚だけ肉があるような網の区間を最大化せよ。

解法

Editorialは3枚重なるケースを排除し、うまくグラフ化してダイクストラに持ち込んだ。
自分は別の解法を取ったので紹介。

焼肉を右端R[i]の位置でソートし、順に置く場合どうなるか考える。
これより左で網に置いてある肉が、L[i]以下の位置にしかないなら、この肉は[L[i],R[i]]の区間分丸ごと1枚の肉だけ来るようになる。
よって、位置xを右端とするような肉の配置におけるおいしく食べられる肉の総長の最大値f(x)をSegTreeで管理し、[0,L[i]]の範囲におけるf(x)のRange Maximum QueryをSegTreeで解けば、その値にR[i]-L[i]を足したものがf(R[i])の候補となる。

一方、右端がすでに[(L[i]+1),(R[i]-1)]に来ている肉の置き方に対し、一部肉を重ねておいても総長が得するケースもあるかもしれないので、そちらも考えなければならない。
右端がx(L[i]＜x＜R[i])であるような肉の配置において、[L[i],R[i]]を覆う肉を置くと、その時のおいしさはf(x)-(x-L[i])+(R[i]-x) = (L[i]+R[i]) + f(x) - 2xとなる。
この最大値を高速に求めるには、g(x) = f(x) - 2xの最大値を求めるSegTreeをもう一つ準備すると良い。

まとめると以下の通りとなる。

• 肉をR[i]順にソート
• 各肉に対して、f(x),g(x)のSegTreeを用いて0≦x≦L[i]におけるf(x)及びL[i]＜x＜R[i]におけるg(x)の最大値からf(R[i])及びg(R[i])を求めていく

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=-10000000;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){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) 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));
	}
	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]);
	}
};

SegTree_1<int,1<<20> st1,st2;
int N,M,ma;
int S[101010],L[101010];
pair<int,int> P[101010];
int V1[101010],V2[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>S[i]>>L[i];
		P[i]={S[i]+L[i],S[i]};
	}
	FOR(i,M+1) st1.update(i,0);
	FOR(i,M+1) st2.update(i,-2000000),V2[i]=-2000000;
	
	sort(P,P+N);
	FOR(i,N) {
		int le=P[i].second;
		int ri=P[i].first;
		
		int hoge1=st1.getval(0,le+1)+ri-le;
		int hoge2=st2.getval(le,ri)+ri+le;
		x = max(hoge1,hoge2);
		ma=max(ma,x);
		
		if(x>V1[ri]) V1[ri]=x, st1.update(ri,V1[ri]);
		if(x-2*ri>V2[ri]) V2[ri]=x-2*ri, st2.update(ri,V2[ri]);
	}
	cout<<ma<<endl;
	
}

まとめ

これは本番割とすんなり解けて、オープン戦ではFAだった。