Crane (POJ 2991) をセグ木コピペで解く

概要

本記事では、 Crane (POJ 2991) を、モノイドの和を計算する通常のセグメント木を使うだけで解く解法を解説する。

事の発端

蟻本を読む某氏「この問題はただセグメント木貼るだけでは解けなそう」
私「なるほど…いや良い感じのモノイド乗せたら出来ないかな…」

私「出来たわ」

Crane 概要

poj.org

蟻本の「3-3 様々なデータ構造を操ろう」 にセグメント木を用いる例として掲載されている。

蟻本では、以下のようにセグメント木を使って実装されている。 (プログラミングコンテストチャレンジブック 第2版 157ページより引用)

各ノードは連続する線分の集合に対応し、次の情報を持たせます。

• 対応する線分たちを、最初の線分を垂直にしてつなげた際の最初の線分の端点から最後の線分の端点へのベクトル。
• (そのノードが子ノードを持つなら) 2つの子ノードの対応する部分をつなげる際に、右の子ノードの部分を回転させる角度。

この実装では、各ノードが「2つの子ノードの間の角度」という、2分木の構造に依存した情報を持っている。 そのため、 単純なモノイド演算として処理することが出来ず、 change 関数内で節点番号を使用した場合分けを行う必要がある。

モノイドを使用した解法

記法

簡単のため、以下では平面上の点およびベクトルを、複素数 で表す。 を虚数単位とし、ベクトル を に対応させる。

セグメント木の構造

セグメント木の各ノードは連続する線分の集合に対応し (蟻本と同じ)、次の情報を持たせる。

• ノードの最初の線分の角度と、ノードの最後の線分の次の線分の角度の差。 ()
• 対応する線分たちを、最初の線分を垂直にしてつなげた際の最初の線分の端点から最後の線分の端点へのベクトル (蟻本と同じ)。 ()

これを として表現する。

(α, a) = (π/2, 2+i) の例。2つの線分が連結されている

(β, b) = (π/4, 3) の例

モノイドの演算

モノイド を考える。モノイドの要素は前述の通り連続する線分の集合を表し、モノイドの演算は連続する線分の集合同士を連結して新たな集合を得ることを表す。

具体的には、演算は

で定義される。

このモノイドは と の外部半直積 (半直積 - Wikipedia) である。 また、今回問題を解く上では使用しないが、この演算には逆元が存在し、 は群となる。

例

以下は のとき、 となることを示した例である。 この和のベクトルの端点は であり、その次の線分は 、すなわち図の左上方向に接続される。

(α, a)・(β, b) = (α+β, a+exp(iα)b)

がモノイドであることの証明

が半直積であることから従うが、明示的な計算で示しておく。

結合律

を示す。

より成り立つ。

単位元の存在

読者の演習課題とする。

解法

このモノイドをセグメント木上に載せることで、元の問題を解く。

1. 番目の線分の長さが であるとき、セグメント木の 個目の葉を で初期化する。
   • このとき、右方向 (実軸正方向) の角度を とするため、便宜的に 番目の葉を として追加する。
2. 線分 と 線分 の間の角を に変更するとき、セグメント木の 個目の葉を に更新する。
3. セグメント木の根が であるとき、 がクレーンの先端の座標を表す。

提出コード

POJなのでC++98で実装した。 上記のモノイドを載せることで、 struct Segtree の定義はライブラリそのままで実装することができた。

#include <cstdio>
#include <cmath>
#include <vector>
#include <complex>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;

// 0-indexed
template <class T, class Op = T (*) (T, T)>
struct Segtree {
  int n;
  vector<T> dat;
  Op op;
  T unit;
  Segtree(int al, Op op = Op(), T unit = T()): op(op), unit(unit) {
    n = 1;
    while(n < al) {
      n *= 2;
    }
    dat = vector<T>(2 * n - 1, unit);
  }
  Segtree(const vector<T> &arr, Op op = Op(), T unit = T()): op(op), unit(unit) {
    int al = arr.size();
    n = 1;
    while(n < al) {
      n *= 2;
    }
    dat = vector<T>(2 * n - 1, unit);
    copy(arr.begin(), arr.end(), dat.begin() + n - 1);
    for(int i=n-2; i >= 0; i--) {
      dat[i] = op(dat[i * 2 + 1], dat[i * 2 + 2]);
    }
  }
  void update(int k, T x) {
    k += n - 1;
    dat[k] = x;
    while(k > 0) {
      k = (k - 1) / 2;
      dat[k] = op(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
  }
  // accumlate [a, b)
  T accum(int a, int b, int k = 0, int l = 0, int r = -1) {
    if(r < 0) r = n;
    if(r <= a || b <= l) return unit;
    if(a <= l && r <= b) return dat[k];
    T vl = accum(a, b, k * 2 + 1, l, (l + r) / 2);
    T vr = accum(a, b, k * 2 + 2, (l + r) / 2, r);
    return op(vl, vr);
  }
};

typedef pair<double, complex<double> > Elem;

struct Add {
  Elem operator()(Elem &a, Elem &b) {
    return make_pair(a.first + b.first, a.second + polar(1.0, a.first) * b.second);
  }
};

int main() {
  double pi = acos(-1.0);
  int n, c;
  while (scanf("%d %d", &n, &c) == 2) {
    vector<Elem> arms;
    arms.reserve(n+1);
    arms.push_back(make_pair(pi / 2.0, complex<double>()));
    REP(i,0,n) {
      double l;
      scanf("%lf", &l);
      arms.push_back(make_pair(0.0, complex<double>(l, 0.0)));
    }
    Segtree<Elem, Add> t(arms, Add(), make_pair(0.0, complex<double>()));
    REP(i,0,c) {
      int s;
      double a;
      scanf("%d %lf", &s, &a);
      t.update(s, make_pair((a - 180.0) / 180.0 * pi, arms[s].second));
      complex<double> &end = t.dat[0].second;
      printf("%.15f %.15f\n", end.real(), end.imag());
    }
    printf("\n");
  }

  return 0;
}

まとめ

• 線分の集合を一様に表現できるモノイド演算を定義し、通常のセグメント木以上の場合分けなどをすることなく解くことが出来た。
• C++98は苦行。