[yukicoder] No. 1226 I hate Robot Arms
問題
https://yukicoder.me/problems/no/1226方針
関節 \( 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;
}
https://kmjp.hatenablog.jp/entry/2020/09/11/0900