Codeforces #303 Div2 C. Woodcutters

CF#303に参加。
Div2にしてもいつもより簡単な回でした。
http://codeforces.com/contest/545/problem/C

問題

N本の木が1列に並んでいる。
それぞれの位置はX[i]、高さはH[i]である。

木を左に倒すとその木は数直線上[(X[i]-H[i])～X[i]]の範囲、右に倒すと[X[i]～(X[i]+H[i])]の範囲を占める。
木を倒さないとその木は点[X[i]]を占める。

複数の木が同じ場所を共有しない範囲で、できるだけ多くの木を左か右に倒したい。
最大何本倒せるか答えよ。

解法

本番は右に倒す場合と倒さない場合のDPを解いたが、もっと簡単に解くことができた。

左側の木から順に以下の通り判定していく。

• 左に倒して左の木と重ならないなら左に倒す。
• 右に倒して右の木と重ならないなら右に倒す。
• どっちにも倒せないならその木は倒さない。

木を右に倒しちゃったら、右の木が左に倒せなくなるが、どちらを倒しても倒せる木の本数は１増えるだけなので、左の木を右に倒してしまってよい。

int N;
ll X[101000],H[101000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>H[i];
	
	int ret=min(N,2);
	
	for(i=1;i<N-1;i++) {
		if(X[i]-H[i]>X[i-1]) {
			ret++;
		}
		else if(X[i]+H[i]<X[i+1]) {
			ret++;
			X[i]+=H[i];
		}
	}
	
	cout<<ret<<endl;
}

まとめ

無駄にDPしちゃったなぁ。