kmjp's blog

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

CODE FESTIVAL 2015 決勝 : D - 足ゲームII

やっぱり自分の解法は大げさかな。
http://code-festival-2015-final-open.contest.atcoder.jp/tasks/codefestival_2015_final_d

問題

N個の区間(S[i],T[i])が与えられる。
どれか1個の区間を取り除けるとき、区間が重なる数の最大値を最小化せよ。

解法

自分はオーバースペックで、範囲に対して加算でき、かつ最大値を取れるSegTreeを使ってしまった。
まず最初にN個分の範囲にそれぞれ1を足し、その後各区間を1個ずつ実際に取り除いて最大値を見た。

もっとラクな方法もあって、まず累積和を使えば各地点を区間が含む数が求まる。
その最大値をMとする。
区間を含む数がMである地点の集合を全部囲う入力の区間があれば、それを取り除けば区間の重なりは(M-1)個になる。
そのような区間が無ければMが解となる。

template<class V,int NV> class SegTree_3 {
public:
	vector<pair<V,int> > val;
	vector<pair<V,int> > ma;
	static V const def=0;
	SegTree_3(){
		int i;
		val.resize(NV*2); ma.resize(NV*2);
		FOR(i,NV) val[i+NV]=ma[i+NV]=make_pair(0,i);
		FOR(i,NV) val[i]=make_pair(0,0);
		for(i=NV-1;i>=1;i--) ma[i]=max(ma[2*i],ma[2*i+1]);
	};
	
	pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return make_pair(def,0);
		if(x<=l && r<=y) return ma[k];
		auto a=max(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
		a.first += val[k].first;
		return a;
	}
	
	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].first+=v;
			ma[k].first+=v;
		}
		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(ma[k*2],ma[k*2+1]);
			ma[k].first += val[k].first;
		}
	}
};

int N;
int S[101010],T[101010];
int num;

SegTree_3<int,1<<18> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<int> P;
	P.push_back(0);
	P.push_back(10000000);
	FOR(i,N) {
		cin>>S[i]>>T[i];
		P.push_back(S[i]);
		P.push_back(T[i]);
	}
	sort(ALL(P));
	P.erase(unique(ALL(P)),P.end());
	FOR(i,N) {
		S[i]=lower_bound(ALL(P),S[i])-P.begin();
		T[i]=lower_bound(ALL(P),T[i])-P.begin();
		st.update(S[i],T[i],1);
	}
	
	int mi=1000001;
	FOR(i,N) {
		st.update(S[i],T[i],-1);
		mi=min(mi,st.getval(0,200200).first);
		st.update(S[i],T[i],1);
	}
	if(mi==0) mi=1;
	
	cout<<mi<<endl;
}

まとめ

端からSweepする案は思いついたけど、M個になる場所が複数あったらどうするか、というのをうまく処理できずSegTreeに行ってしまった。
問題の位置的にそんなややこしいもの要らないとは思ったのだけど…。