yukicoder : No.343 手抜き工事のプロ

まぁ★２ではないよね。
http://yukicoder.me/problems/707

問題

均一な素材でできた、横方向長さLの木材を縦にN個積んでいく。
下からi番目の木材は、左右方向で一番下の木材からX[i]ずれた位置に置かれる。

i番目の木材に対し、それより上の木材群の重心がi番目の木材上及び(i+1)番目の木材上にあるなら、接着せずとも木材は安定する。
そうでないなら、i番目の木材と(i+1)番目の木材を接着しないと安定しない。

木材全体を安定させるためには最小で何組の木材を接着する必要があるか。

解法

上から順に判定していく。
木材群の重心は、各木材の中心の平均位置となるので、i番目と(i+1)番目の木材の接着判定では、(i+1)番より上の木材の中心位置の平均値が何処にあるか判定すればよい。

平均を求める際doubleを使って割り算してもACが解けるが、移行して乗算にした方が整数の範囲で解けて安全。

int N,L;
int X[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L;
	FOR(i,N-1) cin>>X[i+1], X[i+1]+=100000;
	X[0]=100000;
	FOR(i,N-1) if(abs(X[i]-X[i+1])>=L) return _P("-1\n");
	ll tot=0;
	int ret=0;
	for(i=N-1;i>=0;i--) {
		if(i<=N-2) {
			ll mul=2*(N-1-i);
			if(tot<=X[i+1]*mul||(X[i+1]+L)*mul<=tot||tot<=X[i]*mul||(X[i]+L)*mul<=tot) ret++;
		}
		
		tot += 2*X[i]+L;
	}
	cout<<ret<<endl;
}

まとめ

木材木材書いてたら木村に空目してきた。