No.343

設計が破綻しているかどうかは普通に隣り合う鋼材が重なっているかどうか見ればいい.

$i$ 番目の鋼材と $i+1$ 番目の鋼材に溶接が必要かどうかは, $i+1$ 番目より上の鋼材の重心を見ればいい.

重心は,

$$\frac{\sum_{j=i+1}^N (2X_j+L)}{N-j+1}$$

で求められる.

愚直に計算すると $O(N^2)$ かかるが, 上から順に計算していき, 同時に $2X_j + L$ の値の累積和を計算しておくことで $O(N)$ で計算できる.