[yukicoder] No. 1226 I hate Robot Arms

問題

方針

関節 \( i \) の位置を \( P_i = (x_i, y_i) \) とします。初期値は、\( P_i = (i, 0) \) となり、\( P_0 = (0, 0) \) となります。ここで、ベクトル  \( \boldsymbol{v}_i \) を次のように定義します。

\[ \boldsymbol{v}_i =  \overrightarrow{P_iP_{i+1}} \]

\(\boldsymbol{v}_i \) を利用して、\( P_i \ (1 \leq i \leq N)\) は、

\[ P_i = \sum_{k = 0}^{i – 1}\boldsymbol{v}_k \]

と計算できます。

角度の更新クエリ

腕 \(i\) の角度を \(x\) 度に変更すると、\( \theta_i = x \) となり、関節 \( i – 1 \) を始点として \( x \) 度回転することになります。したがって、

\[ \boldsymbol{v}_i = (d_{i+1} \cos\theta_{i+1}, d_{i+1}\sin\theta_{i+1}) \]

と更新されます。\( i + 1 \) 以降の関節は同時に \( x \) 度回転するので、\( \boldsymbol{v}_{i + 1} \) 以降の値は変化しません。

腕の更新クエリ

腕 \(i\) の長さを \(x\) に変更すると、\( d_i = x \) となり、

\[ \boldsymbol{v}_i = (d_{i+1} \cos\theta_{i+1}, d_{i+1}\sin\theta_{i+1}) \]

と更新されます。角度のときと同様に、\( i + 1 \) 以降の関節は同時に平行移動するので、\( \boldsymbol{v}_{i + 1} \) 以降の値は変化しません。

座標のクエリ

\[ P_i = \sum_{k = 0}^{i – 1}\boldsymbol{v}_k \]

を計算して答えます。

セグメント木

\( N \) 個の \( v_i \) の和を セグメント木を用いて、\( 2n – 1 \) 個のノードで管理するとします。\( i \) 番目のノードを \( T_i = (\boldsymbol{w}_i, \alpha_i) \) とし、初めに、

\[ T_{i+ n – 1} = (\boldsymbol{v}_i, \theta_{i + 1}) \ ( 0 \leq i \leq N – 1) \]

とします。これらはセグメント木の最下層のノードになります。次に、\( 0 \leq i \leq n – 2 \) のノードについて、\( T_i = (\boldsymbol{w}_i, \alpha_i) \) とし、

\[ T_{i} = T_{2i + 1} + T_{2i + 2}\]

を構築します。ここで、\( T_{n-1} + T_{n} \) について考えます。これは、\( v_{0} + v_{1} \) を求めることになりますが、

\[ T_{n – 1} + T_{n} \neq (\boldsymbol{v}_i + \boldsymbol{v}_{i + 1}, \theta_1 + \theta_2)\]

となります。腕 \( 2 \) を \( \theta_1 \) 度回転させてから足す必要があるので、回転行列 \( R(\theta) \) を

\[R(\theta) = \begin{bmatrix}
\cos\theta & -\sin\theta \\
\sin\theta & \cos\theta
\end{bmatrix}\]

とすると、

\[ T_{n – 1} + T_{n} = (\boldsymbol{v}_0  + R(\theta_1)\boldsymbol{v}_{1}, \theta_1 + \theta_2)\]

となります。セグメント木を更新クエリのたびに以下の計算を繰り返します。

\[ T_i = (\boldsymbol{v}_{2i+1}  + R(\theta_{2i+1})\boldsymbol{v}_{2i+2}, \alpha_{2i+1} + \theta_{2i+2}) \]

座標のクエリは必ず、\( v_0 \) から足し上げるので、角度による伝播を更新クエリで影響する全てのノードに反映させる必要がないので、遅延評価する必要はありません。

コード

参考