[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 \) から足し上げるので、角度による伝播を更新クエリで影響する全てのノードに反映させる必要がないので、遅延評価する必要はありません。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; double R = acos(-1) / 180; struct Node { double x, y, t; Node(double x, double y, double t) : x(x), y(y), t(t){} }; class SegmentTree { private: int n; vector<Node> node; public: SegmentTree(int N) { n = 1; while (n < N) n *= 2; node.resize(2 * n - 1, Node(0, 0, 0)); for (int i = 0; i < N; i++) { node[i + n - 1].x = 1; } for (int i = n - 2; i >= 0; i--) { node[i] = add(node[2 * i + 1], node[2 * i + 2]); } } Node update(double t, double d) { return Node(d * cos(R * t), d * sin(R * t), t); } Node add(Node v1, Node v2) { double x = v1.x + v2.x * cos(R * v1.t) - v2.y * sin(R * v1.t); double y = v1.y + v2.x * sin(R * v1.t) + v2.y * cos(R * v1.t); return Node(x, y, v1.t + v2.t); } void update_all(int i, double t, double d) { i += n - 1; node[i] = update(t, d); while (i > 0) { i = (i - 1) / 2; node[i] = add(node[2 * i + 1], node[2 * i + 2]); } } Node query(int a, int b, int k = 0, int l = 0, int r = -1) { if (r < 0) r = n; if (b <= l || r <= a) return Node(0, 0, 0); if (a <= l && r <= b) return node[k]; Node v_l = query(a, b, 2 * k + 1, l, (l + r) / 2); Node v_r = query(a, b, 2 * k + 2, (l + r) / 2, r); return add(v_l, v_r); } void disp() { int idx = 0; for (Node i : node) { printf("%d ( %f %f %f)\n",idx, i.x, i.y, i.t); idx++; } } }; int main() { int N, Q; int a, b, x; cin >> N >> Q; vector<Node> ans; SegmentTree st(N); //st.disp(); int t[N]{}, d[N]{}; fill(d, d + N, 1); for (int i = 0; i < Q; i++) { cin >> a >> b; if (a == 2) { Node p = st.query(0, b); ans.push_back(p); } else { cin >> x; if (a == 0) { t[b - 1] = x; } else { d[b - 1] = x; } st.update_all(b - 1, t[b - 1], d[b - 1]); } } for (Node p : ans) { printf("%.9f %.9f\n", p.x, p.y); } //st.disp(); return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません