kmjp's blog

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

Good Bye 2014 : E. New Year Domino

Codeforces

発想はいいところまで行ったのに、最後までバグがとりきれなかったのが残念。
http://codeforces.com/contest/500/problem/E

問題

N個のドミノが２次元座標上に並んでいる。
Y座標は高さ方向の向きであり、Y=0が地面とする。

今見ている向きでは、各ドミノは座標(P[i],0)を下端として高さL[i]の棒であるように見える。
各ドミノを右側に倒すと、X座標xがP[i]≦x≦P[i]+L[i]の範囲にあるドミノも連鎖的に倒れる。

ここでQ個のクエリに答えよ。

各クエリは(X[i],Y[i])の２値で与えられる。
X[i]番のドミノを倒したとき、Y[i]も倒れるようにしたい。
ただし途中ドミノの高さが足りずY[i]が倒れないかもしれない。
その場合、コスト1で任意の１つのドミノの高さを1増やすことができる。
Y[i]を倒す最小コストを求めよ。

解法

BIT+ダブリングで解くことができる。

まず、BITを用いて(高さを増すことなく)各ドミノを倒した場合、連鎖的に倒せない最もX座標の小さなドミノの番号Rnext[i]を求める。
これはiを大きい順位処理していくことで解ける。
lower_bound等を用いてi番のドミノで直接倒せない(P[x]＞P[i]+L[i]である)最小のxを求める。これをR[i]とする。
後はBITを用いてRnext[i]=max(R[x], Rnext[i+1], Rnext[i+2] , ... , Rnext[R[x]-1])を求めることができる(2項目以降のRnextの最大値にBITを用いる)

次に、i番のドミノがRnext[i]を倒すために必要な高さの上昇量Cnext[i]を求める。
i番で直接倒すことを考えるなら、Cnext[i]=P[Rnext[i]]-P[i]-L[i]である。
また、i番からRnext[i]番の間の他のドミノの高さを変えることを考えると、Rnext[j]==Rnext[i]であるようなjにおいて、Cnext[i]=min(Cnext[j])でもよい。

これで、どこか高さを変えないと届かない最も近いドミノRnext[i]とそのコストCnext[i]を求めることができた。

次に各クエリに対する処理だが、X[i]=Rnext[X[i]]による変換を繰り返してX[i]≧Y[i]となるまでどんどんドミノを辿って行き、その際Cnext[X[i]]を加算していけば良い。
ただ、これだけだとTLEするのでダブリングを併用する。


なお、自分が本番うまく行かなかった理由は、Cnext[i]の計算の際Rnext[j]!=Rnext[i]であるjも対象にして最小値を求めてしまったせいだった。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	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<ll,1<<19> st;

int N;
ll P[202000],L[202000];
ll R[202000];
ll RN[20][202000],CN[20][202000];
ll mic[202000];
int Q;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i]>>L[i];
	
	P[N]=1LL<<40;
	RN[0][N]=N;
	st.update(N+1,N);
	FOR(i,N+1) mic[i]=1LL<<40;
	for(i=N-1;i>=0;i--) {
		R[i]=lower_bound(P,P+N+1,P[i]+L[i]+1)-P;
		RN[0][i]=max(R[i],st.getval(0,R[i]+1));
		
		CN[0][i]=min(P[RN[0][i]]-P[i]-L[i],mic[RN[0][i]]);
		mic[RN[0][i]]=min(mic[RN[0][i]],CN[0][i]);
		st.update(i+1,RN[0][i]);
	}
	FOR(x,18) FOR(i,N+1) RN[x+1][i]=RN[x][RN[x][i]], CN[x+1][i]=CN[x][i]+CN[x][RN[x][i]];

	cin>>Q;
	while(Q--) {
		cin>>l>>r;
		l--,r--;
		ll ret=0;
		for(i=18;i>=0;i--) if(RN[i][l]<=r) ret+=CN[i][l], l=RN[i][l];
		while(RN[0][l]<=r) ret+=CN[0][l], l=RN[i][l];
		cout<<ret<<endl;
	}
	
}

まとめ

こちらも問題設定・解法ともに割と好み。
解けなかったのが悔やまれるな。